|
|
Cette partie presente le Travail d'Etude et de Recherche, que j'ai realise avec Johann Pelfrene,
en 1998-1999, durant ma maitrise d'informatique, a l'Universite de Rouen.
abstract
|
 |
 |
|
La comparaison de deux séquences (mots) quelconques peut se faire sur la base du nombre d'opérations d'édition nécessaires pour passer d'un mot à l'autre.
Les opérations d'édition autorisées sont :
- le remplacement d'une lettre par une autre,
- la suppression d'une lettre,
- l'ajout d'une lettre.
Le nombre minimum d'opérations nécessaire pour transformer une séquence en une autre est une distance. On peut calculer cette distance pour deux séquences en utilisant un algorithme basé sur la programmation dynamique, qui repose sur un ensemble de relations de récurrence. Cet algorithme est très utilisé en biologie moléculaire pour comparer des séquences d'ADN de différents organismes vivants.
L'objectif de ce projet consiste à implémenter :
- d'abord quelques algorithmes (Needleman & Wunsch, Smith & Waterman, Lars Arvestadt) qui permettent de se familiariser avec les différents types de problèmes rencontrés,
- puis, une modification des relations de récurrence de cet algorithme qui permet de prendre en compte les trois aspects suivants en même temps :
- les séquences d'ADN (mots sur un alphabet de quatre lettres) contiennent des sous-séquences qui représentent le codage de proteïnes (mots sur un alphabet de 20 lettres).
- Les séquences d'organismes vivants disponibles sous forme de fichiers textes contiennent parfois des erreurs dues à une mauvaise lecture en laboratoire, ces erreurs affectent la traduction du codage de l'ADN en proteïnes.
- Les similitudes entre deux séquences ne concernent souvent que des segments limités de ces séquences.
|
|
| |
Documentation
|
|
|
Cette partie presente le rapport et sa soutenance, ainsi que le code correspondant a ce travail.
|
|
| |
|
|
