\chapter{Codes}

\section{Alignements stucturaux}

\subsection{Alignement de deux séquences et alignements multiples}

Nous avons commencé à nous interroger sur comment pouvait-on aligner deux séquences.
\\Le principe de l'alignement de séquence est de pouvoir comparer deux ou plusieurs séquences entre elles. A partir d'une séquence (généralement la plus longue), on regarde la correspondance optimal entre chaques éléments des différentes séquences.
\\Dans notre cas présent, nous avons utilisé la méthode de Needleman-Wunsch avec la matrice de similitude BLOSUM62.
\\La méthode de Needleman-Wunsch se base sur le fait qu'il existe trois possibilités à un aligement de deux séquences:
\begin{itemize}
\item[-] Soit l'élément à la i-ème position d'une des deux séquences s'apparie avec le i-ème élément de la seconde séquence.
\item[-] Soit le i-ème élément de la première séquence ne s'apparie pas avec le i-ème élément de la seconde séquence, dû à une insertion ou une délétion d'un élement, créant ainsi un "gap".
\item[-] Soit le i-ème élément de la seconde séquence ne s'apparie pas avec le i-ème élément de la première séquence, créant ainsi un gap en face de cet élément.
\end{itemize}
Le choix entre ces trois possibilités se repose sur l'optimisation du score de cet étape en regardant dans la matrice de similitude le coût de cet alignement. Ainsi, en mettant un coût arbitraire à la création d'un gap (-8), nous comparons ceci au coût de la première proposition aux deux autres.
\\Ainsi, nous créons une réflexion en boucle, commençant par l'extrémité d'une des séquences et en continuant notre lecture jusqu'à ce qu'il n'y est plus d'éléments à aligner. En calculant le score maximal que l'on peut obtenir dans chaque case d'un tableau à double entrées avec chacune des séquences en entrée, nous pouvons créer un chemin en additionnant ces scores calculés et ainsi arriver à un score maximal pour l'alignement de chaque élément des deux séquences. En remontant ce résonnement, nous arrivons à un alignement dit optimal, le moins coûteux. 
\\De plus, nous avons remarqué qu'il serait plus coûteux d'ouvrir un gap dans une sequence que d'en continuer un (i.e le i-ème élément de la première ou seconde séquence ne s'aligne pas après plusieurs pas consécutif avec l'autre séquence. Cette réfléxion est due au fait que la continuation d'un gap n'a pas être aussi coûteux que l'ouverture d'un car le néo-gap sera placé à un endroit où la possibilité d'insertion ou de délétion est plus probable (ceci s'est déjà produit).
\\Notre code pour l'alignement de deux sequences:
\\
\\
\\
\\
\\Pour passer de l'alignement de deux séquences à de l'alignement multiple, nous avons procédé par étapes:
\begin{enumerate}
\item Alignements des séquences par paires avec pour chaque couple un score d'alignement.
\item Création d'un arbre guide par comparaison entre les scores des différentes paires.
\item Alignement des différents clusters entre eux avec addition des scores pour avoir un alignement final de toutes les séquences. 
\end{enumerate}

\subsection{Clustering}

La création des clusters suite à l'alignement par paires se repose sur la proximité des alignements entre eux. Ceci est décidé par la valeur des scores obtenus et des scores totaux lors de l'alignement de différents clusters entre eux. L'aligement d'une séquence avec un alignement déjà fait s'effectue de la même manière qu'un alignement de deux séquences mais nous ne regardons plus l'appariement de deux éléments mais celui d'un élément avec un groupe d'éléments déjà formé. Ainsi, le score obtenu ne sera pas celui de la comparaison entre deux éléments mais de l'addition des scores entre cet élément et chaque éléments du groupe.
Ainsi, nous pouvons créer un arbre guide dont la distance entre chaque cluster peut être indiqué.
Notre code pour la création de l'arbre guide:
\\
\\
\\

\subsection{Ajout de l'information structural}

Grâce au format PDB, nous pouvons comparer les différentes structures des protéines. Ainsi, pour certains paramètres comme la pénalité de gap, cette nouvelle information induira leur changement. En effet, si l'on considère un acide aminé qui serait structurellement à l'intérieur de la structure tridimensionnelle,la création d'un gap semble beaucoup moins probable. Du coup, le coût de création de gap sera plus élevé que pour l'alignement d'un acide aminé qui serait situé dans une boucle à la surface de la protéine.

Notre code pour l'introduction de l'information structurale:
\\
\\
\\
\\

\section{Protéines à P-loop}