Analyse bioinformatique des séquences

5. - La comparaison de séquences
5.6 - Le logiciel FASTA

Les différentes étapes de l'algorithme

Pour chaque séquence de la banque, l'algorithme se déroule en quatre étapes sélectives distinctes qui permettent de cibler rapidement et précisément les régions intéressantes pour l'alignement optimal.

• La première étape consiste à repérer les régions les plus denses en identités partagées par les deux séquences. La codification numérique des séquences est ici utilisée avec une longueur des segments codés noté ktup. Cette étape confère à l'algorithme l'essentiel de sa rapidité.
• Dans une deuxième étape, on recalcule à l'aide d'une matrice de scores élémentaires un score pour les dix meilleurs régions d'identité trouvées dans l'étape précédente en considérant éventuellement des associations non exactes entre certains éléments des séquences. Pour les protéines, on utilisera ici une matrice de substitution. Cette deuxième étape correspond donc à une recherche de similitudes sans insertion-deletion uniquement sur les régions de haute identité. Les scores obtenus correspondent à des régions initiales de premier ordre et l'on qualifie de score init1 celui qui représente la région de plus fort score parmi les dix analysées.
• La troisième étape essaie de joindre les régions définies à l'étape précédente, bien entendu s'il en existe au moins deux et si chacune de celles-ci possède un score supérieur à un score seuil prédéfini. Ce seuil correspond en fait à un score moyen attendu pour des séquences non apparentées. On réunira ces régions initiales à chaque fois que la somme de leur scores diminuée d'une pénalité de jonction est supérieure ou égale au score init1. Ce score s'il existe est appelé initn et correspond à une région initiale de deuxième ordre.
• La quatrième étape consiste à effectuer l'alignement optimal de la séquence recherchée avec la séquence de la banque en considérant uniquement les parties des séquences délimitées par la meilleure région initiale de score initn (qui est égale à init1 s'il n'y a pas eu de jonction à l'étape 3). On obtient alors un score optimal dénommé opt. Cet alignement est effectué uniquement pour un nombre limité de séquences fixé par l'utilisateur. Ce sont les séquences qui correspondent aux plus hauts scores initiaux initn.