|
|
Résultat majeur : AVERAGE COMPLEXITY OF THE JIANG-WANG-ZHANG PAIRWISE TREE ALIGNMENT ALGORITHM AND OF A RNA SECONDARY STRUCTURE ALIGNMENT ALGORITHM |
 |
|
 |
|
AVERAGE COMPLEXITY OF THE JIANG-WANG-ZHANG PAIRWISE TREE ALIGNMENT ALGORITHM AND OF A RNA SECONDARY STRUCTURE ALIGNMENT ALGORITHM
01 juin 2010
Claire Herrbach, Alain Denise and Serge Dulucq. Theoretical Computer Science 411 (2010) 2423-2432.
|
We prove that the average complexity of the pairwise ordered tree alignment algorithm of Jiang, Wang and Zhang is in O(nm), where n and m stand for the sizes of the two trees, respectively. We show that the same result holds for the average complexity of RNA secondary structure alignment.
Activités de recherche
° Algorithmique ° Bioinformatique ° Combinatoire
Equipe
° Bioinformatique
Contact
° DENISE Alain
|
| |
|
|
|
|
