|
|
Résultat majeur : THE AVERAGE COMPLEXITY OF TREE ALIGNMENT |
 |
|
 |
|
THE AVERAGE COMPLEXITY OF TREE ALIGNMENT
28 janvier 2008
Nous avons démontré que la complexité moyenne de l'algorithme d'alignement d'arbres de Jiang, Wang et Zhang (1995) est en O(n^2).
|
Le fait étonnant est que la complexité moyenne de l'alignement d'arbres est du même ordre que celle de l'alignement de séquences ! Ce résultat se généralise au calcul de la complexité de l'alignement de structures secondaires d'ARN. Référence : Claire Herrbach , Alain Denise , Serge Dulucq, Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm, Proceedings of MACIS 2007.
Activités de recherche
° Algorithmique ° Bioinformatique ° Combinatoire
Equipe
° Bioinformatique
Contact
[aucun]
|
| |
|
|
|
|
