Méthodes de comparaison entre séquences

multi-échelles végétales

Sylvain DEMEY

Introduction

Séquençage haut débit → forte augmentation des données

Besoin d’outils d’analyses de comparaison Même besoin en biologie végétale au niveau de

l’architecture des plantes Objectifs: implémentation d’un nouvel algorithme de

comparaison entre séquences multi-échelles dans le cadre du logiciel AMAPmod

comparaison de 2 méthodes

1.Le contexte et le travail demandé

Architecture des plantes

Description d’un individu avec au moins 1 des informations suivantes:

Information géométrique Information topologique décrivant les connections

entre les entités Information de décomposition

entre-noeud

Unité de croissance

Modélisation de l’architecture des plantes

Description arborescente (plus complexe) Description sous la forme de séquences

Exemple de séquence

00 1 0000

0

0

0

0

0

0

1

( )( )( )Multi-échelles

Pourquoi la notion de séquence multi-échelles?

01010101010

01010101010

(0101)(0101010) (0101010)(1010)

Les ordres de ramification

ORDRE 1 (Tronc)

ORDRE 2

ORDRE 3

ORDRE 4

Travail demandé

Doit pouvoir s’intégrer dans AMAPmod (dans la librairie Treematching)

Implémentation d’une méthode de comparaison globale

De comparaison locale Algorithme pour la comparaison

d’arborescences appliqué à la comparaison de séquences

Analyses

2. Algorithmes de comparaison de séquences et implémentation

Algorithmes utilisés et développés

Wagner-Fisher (74): alignement global Smith-Waterman (81): alignement local Selkow (77): méthode de comparaison entre

arborescences (utilisé pour la comparaison de séquences multi-échelles)

Construction des chaînes parenthésées

T1 T2 T3

T= ((001) (0001) (1010)) (

)

) ( ) ( )

)

La comparaison d’arborescences

T1 T2

insertion de e

substitution de a

substitution de b

délétion de d

substitution de a

Les contraintes de l’algorithme de Selkow

Les contraintes de l’algorithme de Selkow

Les contraintes de l’algorithme de Selkow

Selkow

Algorithme récursif Utilise Wagner-Fisher pour la comparaison

entre sous-arbres Insertion d’un sous-arbre Délétion d’un sous-arbre

Implémentation

Langage C++ Qt pour l’interface R pour les analyses Coût des opérations d’édition:

0 ou 1

Présentation du logiciel

Les résultats pour l’alignement global

Les résultats pour l’alignement de séquences multi-échelles

Exemple de gestion des load/save

Exemple de gestion des erreurs

3. Analyses

Modèle théoriqueModèle " simple " :

0 10,50,5 0,5

0,5

Modèle "multi-échelle" 1

0 1

0,40,4 0,4

0,4

0’ 1’

Modèle " multi-échelle " 2

0 10,40,4

0,3

0,3

0’ 1’

0,2

0,50,5

0,5

0,5

0,2

0,3

0,15 0,3

0,15

0,5 0,30,4

0,5

Les méthodesWagner-Fisher Selkow

Les exemples choisis

Braeburn Fuji Sur les 5 premiers ordres Chaque ordre 3 types (uc, axil, uc1 axil) Alignement global/Alignement de séquences

multi-échelles

Format des données

Exemple sur l’ordre 1

Wagner-Fisher Selkow

Interprétations sur ordre1

L’ordre 1 → le plus représentatif Bonne séparation mais généralement

meilleure avec Selkow Tjrs à peu près les mêmes intrus sur les 3

types Groupe vaste/groupe compact

Conclusion et perspectives

Conclusion

Implémentation d’une nouvelle méthode de comparaison de séquences multi-échelles

Validation de la méthode par des analyses Séparation suivant les espèces Apprentissage du C/C++, de Qt et du

clustering avec R

perspectives

Nouvelles matrices d’édition Intégration dans AMAPmod Analyses des résultats des alignements Autre application botanique: validation de

modèles Application dans d’autres domaines: Exemple structure secondaire de l’ARN

Exemple

Epingle à cheveux (élément de structure secondaire)

On peut représenter cet élément de structure sous la forme de la séquence :

(AAUCC) [AUUGCACUCC] (GGAUU)