Etude et implémentation d’un algorithme d’alignement de

séquences

Soutenu par : Cédric Bonnier et Marion Carrier

24/03/2011

Introduction

Outil d’alignement de séquences

Performances

Validation et tests

2

Plan

I. Les objectifs1. Principe général2. Format d’entrée de la banque3. Séquence d’ADN inconnue

II. La solution implémentée1. Organisation de la solution2. Transformation des données3. Recherche de solutions

III. Les tests réalisés1. Influence de la taille de la séquence connue2. Influence de la taille du fragment cherché3. Influence de la marge d’erreur

3

1. Principe général

4

I. Les objectifs II. La solution implémentée III. Les tests réalisés

2. Format d’entrée de la banque

5

Banque de données de séquences d’ADN

33ATCCGATCTAAATCATCCGATCTATCCGATCTA

Séquences d’ADN connues

…

…

…

…

…

…

I. Les objectifs II. La solution implémentée III. Les tests réalisés

3. Séquence d’ADN inconnue

6

ACTGTAGCCT…1 ACT3 TGT8 CCT…

Format de représentation habituel des séquences

Nouveau format utilisé

Liste de marqueurs

I. Les objectifs II. La solution implémentée III. Les tests réalisés

1. Organisation de la solution

7

Programmes

Transformation

Recherche

310 0 00 0 011 0 0…

Solution trouvée :…

Langage C

I. Les objectifs II. La solution implémentée III. Les tests réalisés

2. Transformation des données

Mise des séquences sous forme de tableau

Calculs binaires

ACTACCAACT

6

1ACTA

24 2

1ACTAC

33 3

2

8

I. Les objectifs II. La solution implémentée III. Les tests réalisés

2. Transformation des données

Sauvegarde des nouvelles données

Fichiers binaires

3 7001 12 00 0 02 6 154 5 0

01001 ......

9

I. Les objectifs II. La solution implémentée III. Les tests réalisés

3. Recherche de solutions

Transformation des données sur les marqueurs

Calculs binaires

Marge d'erreur = 2

Transformation en indices

Transformation en intervalles

10

I. Les objectifs II. La solution implémentée III. Les tests réalisés

Recherche des marqueurs dans les séquences des banques de données

Utilisation d'une pile

Intervalle dans la séquence connue

Taille de la séquence connue : 100Taille de la séquence

cherchée : 36

2 12 23 48 60

33 4 50 60

9 15 40 82

[ 23 ; 27 ]

[ 57 ; 61 ]

Solution

[ 10 ; 78 ]

[ 48 ; 52 ]

11

I. Les objectifs II. La solution implémentée III. Les tests réalisés

3. Recherche de solutions

1. Influence de la taille de la séquence connue

12

Solution uniqueEntre 2 et 5 solutionsPlus de 5 solutionsNombre de solutions nulPas assez d’informations20 000 nucléotides 10 000 nucléotides

5 000 nucléotides

I. Les objectifs II. La solution implémentée III. Les tests réalisés

13

Solution uniqueEntre 2 et 5 solutionsPlus de 5 solutionsNombre de solutions nulPas assez d’informations500 nucléotides 1 000 nucléotides

2 000 nucléotides

I. Les objectifs II. La solution implémentée III. Les tests réalisés

2. Influence de la taille du fragment cherché

14

Solution uniqueEntre 2 et 5 solutionsPlus de 5 solutions

Marge nulle 3 nucléotides

6 nucléotides

I. Les objectifs II. La solution implémentée III. Les tests réalisés

3. Influence de la marge d’erreur

Conclusion

Approche différente du problème

Programmation en vue des performances

Améliorations possibles

Point de vue d’un biologiste

15