Algorithme Bio (Adn)

[Étienne9]

Bonjour,

 

Je révise car j'ai un examen demain matin...

Et je suis en train de regarder les annales.

http://doc-bd.univ-lille1.fr/examens/examenpdf/2011/02IFM1AA11.pdf

Pour la partie "Algorithmes Bio", je n'arrive pas à faire la question 2 et 3 de l'exercice 4.

Et plus, je ne parviens pas à faire tout l'exercice 5.

 

Quelqu'un pourrez m'aider s'il vous plaît ?

Enfin, m'expliquer comme s'y prendre ?

 

Merci

[Étienne9]

Pour l'adaptation j'ai sans doute une piste.

J'aimerais savoir ce que vous en pensez.

 

Il faut considérer une matrice de similarité où la diagonale est à 1 (AA, BB,CC,DD... etc), tout le reste à 0.

Pour un trou, la pénalité est de 0.

On considère 2 séquences n et m dont m est la séquence la plus longue.

On fabrique un tableau de taille n, chaque case est une liste de mots.

Donc dans la case i, il y aura tous les facteurs communs de taille i.

tant que la chaine n n'est pas vide (qu'il n'y a pas que des -)

On applique l'algorithme de Needleman et Wunsch et on suppose qu'il retourne une liste qui contient toutes les positions où les comparaisons ont échouées.

À partir de ces positions, on peut extraire des facteurs communs (entre chaque position) et leur taille. Il faut les ajouter dans les listes en question données par le tableau préalablement créé.

décaler la séquence n d'un cran à droite (ou à gauche mais il faut une fois choisi, qu'on ne change pas de sens)

fin tant que

 

Vous en pensez quoi ?