\documentclass{slides}

\newcommand{\head}[1]{\begin{center}\textbf{#1}\end{center}}

\pagestyle{empty}

\begin{document}
\title{A Survey of Bioinformatics}
\author{Humberto Ortiz Zuazaga \\
University of Texas Health Science Center at San Antonio \\
\texttt{humberto@momo.uthscsa.edu} \\
\texttt{http://momo.uthscsa.edu/\~{}humberto/cmb/}
}
\date{May 8, 1997}
\maketitle

%%%
\begin{slide}
\head{Bioinformatics} 

The application of computers to the collection, analysis, and
presentation of biological information.
\end{slide}

%%%
\begin{slide}
\head{Taxonomy (of the talk)}
\begin{itemize}
\item Sequence analysis
\item Structure prediction
\item Genetic and physical mapping
\item Gene expression networks
\item Biological databases
\item Biological software components
\end{itemize}
\end{slide}

%%%
\begin{slide}
\head{Sequence analysis}
\begin{itemize}
\item Pairwise sequence alignment
\item Multiple sequence alignment
\item Phylogenetic analysis
\item Gene prediction
\end{itemize}
\end{slide}

\begin{slide}
\head{Pairwise sequence alignments}
Given a pair of sequences over an alphabet $\Sigma$, and a cost
function that assigns a cost to an alignment, find an alignment of the
strings that minimizes the cost.
\begin{itemize}
\item This problem is central to many biological programs (homology
  searches, multiple alignments, molecular phylogeny, exon prediction,
  protein threading, ...)
\item Usually solved by Dynamic Programming.
\end{itemize}
\end{slide}


%%%
\begin{slide}
  \head{Multiple sequence alignments}
  \begin{itemize}
  \item Assign a cost to alignments of multiple sequences.
  \item Sum of pairs metric, add all pairwise alignments together.
  \item NP-complete for the SP metric.
  \item Other heuristics must be used for practical programs (Divide
    and Conquer, HMM's).
  \end{itemize}
\end{slide}

%%%
\begin{slide}
\head{Structure prediction}
\begin{itemize}
\item Theoretical models of protein folding
\item Statistical models of protein folding
%\item RNA secondary structure prediction
\end{itemize}
\end{slide}

%%%
\begin{slide}
  \head{The H-P model of globular proteins}
\begin{itemize}
\item Amino acids are hydrophobic (H, nonpolar) or hydrophilic (P,
  polar).
\item H-H contacts contribute -1 to the energy of the protein.
\item all other contacts contribute 0.
\item Protein structures are constrained to self-avoiding paths on a
  regular lattice.
\end{itemize}

\end{slide}

%%%
\begin{slide}
\head{The Inverse Protein Folding (IFP) problem}
Given a target structure or conformation of a protein $G$, find a
sequence $s$ of length $n$ that:
\begin{itemize}
\item Has $G$ as is it's minimum energy state.
\item Has the lowest degeneracy (number of other conformations with
  the same energy) of any possible sequence.
\end{itemize}
\end{slide}

%%%
\begin{slide}
\head{The Heuristic Sequence Design (HSD) problem}
IFP is conjectured to be NP-complete, the best known algorithm must
search over all possible conformations of all possible sequences.  HSD
problems try to simplify the computation by restricting the problem.
\begin{itemize}
\item The Canonical Method: find the sequence with at most $\lambda
  n$ hydrophobic residues.
\item The Grand Canonical Method: Change the energy function so that
  H-H contacts have -2, an exposed H residue has 1, and all other
  interactions have 0.
\end{itemize}
\end{slide}

\begin{slide}
\head{Computational Results}
\begin{itemize}
\item The Canonical Method is NP-complete (reduction from
  SUBSET-SUM), but there are algorithms that can approximate the
  energy of the optimal solution (OPT) to 1+OPT on 2D lattices, and 1/2
  OPT on 3D lattices.
\item The Grand Canonical Method can be solved in polynomial time.
\end{itemize}
\end{slide}

%%%
\begin{slide}
  \head{Protein Threading}
  \begin{itemize}
  \item Divide each sequence into functional domains (by multiple
    alignments).
  \item Thread each domain into a structure from a library of similar
    domains.
  \item Compute a ``pseudo-energy'' based on the empirically
    determined probabilities that each structural unit in the protein
    would be in the structural environment it is in.
  \end{itemize}
\end{slide}

%%%
\begin{slide}
  \head{Genetic and physical mapping}
  \begin{itemize}
  \item Maximum likelihood mapping
  \item Breakpoint mapping
%  \item Restriction mapping
%  \item Shotgun sequencing
  \item Sequencing by hybridization
  \end{itemize}
\end{slide}

%%%
\begin{slide}
  \head{Gene expression networks}
  \begin{itemize}
  \item Complete genomes available for several species.
  \item 100,000 human genes, many already sequenced.
  \item Large scale synthesis of thousands of oligo probes.
  \item Biologists will soon be able to measure expression levels for
    ALL GENES in a single assay.
  \end{itemize}
\end{slide}

%%%
\begin{slide}
\head{Biological databases}
\begin{itemize}
\item ACEDB
\item ECO-CYC
\end{itemize}
\end{slide}

%%%
\begin{slide}
  \head{Biological software components}
  \begin{itemize}
  \item bioTk
  \item bioWidgets for Java
  \item bioViews
  \end{itemize}
\end{slide}

\end{document}

%%%
\begin{slide}
  \head{}

\end{slide}
