Utiliser latex pour expliquer la programmation dynamique

Vous voulez faire découvrir la programmation dynamique à des lycéens ? Rien de mieux qu’une petite présentation… En bon geek, vous allez la faire en latex. Mais pour ça, il va falloir connaître quelques ficelles, surtout quand on veut pouvoir représenter la façon dont on remplit la matrice, pas à pas:

Pour que ce soit lisible, j’ai mis le code ici, sur gist.github. Une fois que vous l’avez récupérer, lancez la commande « pdflatex », vous obtiendrez un document comme ça: dynamic_programming.
\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{url}</code>

\setbeamertemplate{navigation symbols}{}

\setbeamertemplate{footline}[page number]

\title{About optimal sequence alignment}
\subtitle{A short glimpse into bioinformatics}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\frametitle{Pairwise sequence alignment}
Assumptions:
\begin{itemize}
\item sequences $S_1$ and $S_2$ are homologous, they share a common ancestor;
\item differences between them are due to only two kinds of events, substitutions and insertion-deletions.
\end{itemize}

Strategy:
\begin{itemize}
\item choose a scoring matrix (reward for match, penalty for mismatch and gap);
\item compute the editing distance (number of matches, mismatches and gaps) to go from one sequence to the other;
\item keep the alignment with the highest score.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Needleman-Wunsch algorithm}
\begin{itemize}
\item Aim: find the optimal global alignment of sequences $S_1$ and $S_2$
\item Recursion rule:
\begin{align}
D(i,j) = max
\begin{cases}
D(i-1,j-1) + score( S_1[i], S_2[j] )\\
D(i-1,j) + gap\\
D(i,j-1) + gap
\end{cases}
\end{align}
\item Scoring scheme: identity=0 transition=-2 transversion=-5 gap=-10
\item Sequences: $S_1$=TTGT $S_2$=CTAGG
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Fill the matrix}
\begin{tabular}{l|cccccccccccc}
&amp; &amp; &amp; C &amp; &amp; T &amp; &amp; A &amp; &amp; G &amp; &amp; G \\ \hline
&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; \\
&amp; \visible{0} &amp; \visible{$\rightarrow$} &amp; \visible{-10} &amp; \visible{$\rightarrow$} &amp; \visible{-20} &amp; \visible{$\rightarrow$} &amp; \visible{-30} &amp; \visible{$\rightarrow$} &amp; \visible{-40} &amp; \visible{$\rightarrow$} &amp; \visible{-50} \\
&amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \\
T &amp; \visible{-10} &amp; \visible{$\rightarrow$} &amp; \visible{-2} &amp; \visible{$\rightarrow$} &amp; \visible{-10} &amp; \visible{$\rightarrow$} &amp; \visible{-20} &amp; \visible{$\rightarrow$} &amp; \visible{-30} &amp; \visible{$\rightarrow$} &amp; \visible{-40} \\
&amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \\
T &amp; \visible{-20} &amp; \visible{$\rightarrow$} &amp; \visible{-12} &amp; \visible{$\rightarrow$} &amp; \visible{-2} &amp; \visible{$\rightarrow$} &amp; \visible{-12} &amp; \visible{$\rightarrow$} &amp; \visible{-22} &amp; \visible{$\rightarrow$} &amp; \visible{-32} &amp; \\
&amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \\
G &amp; \visible{-30} &amp; \visible{$\rightarrow$} &amp; \visible{-22} &amp; \visible{$\rightarrow$} &amp; \visible{-12} &amp; \visible{$\rightarrow$} &amp; \visible{-4} &amp; \visible{$\rightarrow$} &amp; \visible{-12} &amp; \visible{$\rightarrow$} &amp; \visible{-22} &amp; \\
&amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \visible{$\searrow$} &amp; \visible{$\downarrow$} &amp; \\
T &amp; \visible{-40} &amp; \visible{$\rightarrow$} &amp; \visible{-32} &amp; \visible{$\rightarrow$} &amp; \visible{-22} &amp; \visible{$\rightarrow$} &amp; \visible{-14} &amp; \visible{$\rightarrow$} &amp; \visible{-9} &amp; \visible{$\rightarrow$} &amp; \visible{-17} &amp;
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Traceback}
\begin{tabular}{l|cccccccccccc}
&amp; &amp; &amp; C &amp; &amp; T &amp; &amp; A &amp; &amp; G &amp; &amp; G \\ \hline
&amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp; \\
&amp; \color{red}{0} &amp; $\rightarrow$ &amp; -10 &amp; $\rightarrow$ &amp; -20 &amp; $\rightarrow$ &amp; -30 &amp; $\rightarrow$ &amp; -40 &amp; $\rightarrow$ &amp; -50 \\
&amp; $\downarrow$ &amp; \color{red}{$\searrow$} &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \\
T &amp; -10 &amp; $\rightarrow$ &amp; \color{red}{-2} &amp; $\rightarrow$ &amp; -10 &amp; $\rightarrow$ &amp; -20 &amp; $\rightarrow$ &amp; -30 &amp; $\rightarrow$ &amp; -40 \\
&amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \color{red}{$\searrow$} &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \\
T &amp; -20 &amp; $\rightarrow$ &amp; -12 &amp; $\rightarrow$ &amp; \color{red}{-2} &amp; \color{red}{$\rightarrow$} &amp; \color{red}{-12} &amp; $\rightarrow$ &amp; -22 &amp; $\rightarrow$ &amp; -32 &amp; \\
&amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \color{red}{$\searrow$} &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \\
G &amp; -30 &amp; $\rightarrow$ &amp; -22 &amp; $\rightarrow$ &amp; -12 &amp; $\rightarrow$ &amp; -4 &amp; $\rightarrow$ &amp; \color{red}{-12} &amp; $\rightarrow$ &amp; -22 &amp; \\
&amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; $\searrow$ &amp; $\downarrow$ &amp; \color{red}{$\searrow$} &amp; $\downarrow$ &amp; \\
T &amp; -40 &amp; $\rightarrow$ &amp; -32 &amp; $\rightarrow$ &amp; -22 &amp; $\rightarrow$ &amp; -14 &amp; $\rightarrow$ &amp; -9 &amp; $\rightarrow$ &amp; \color{red}{-17} &amp;
\end{tabular}
\end{frame}

\begin{frame}[fragile]
\frametitle{Output}
Plot the optimal alignment:
\begin{verbatim}
CTAGG
*| |*
TT-GT
\end{verbatim}

Score: -17

Complexity in time: $O(nm)$

Complexity in memory: $O(nm)$
\end{frame}

\begin{frame}
\frametitle{Acknowledgments}
Bellman; Levenstein; Needleman and Wunsch; Sankoff and Sellers; Hirschberg; Smith and Waterman; Gotoh; Ukkonen, Myers and Fickett; and many others...

\vspace{1cm}
Want to know more? start reading!
\url{http://lectures.molgen.mpg.de/online_lectures.html}
\end{frame}

\end{document}

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :