Towards distance-based phylogenetic inference in average-case linear-time

Abstract : Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly , on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given distance threshold. This paper includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a widely used phylogenetic inference method.
Type de document :
Communication dans un congrès
International Workshop on Algorithms in Bioinformatics, Aug 2017, Boston, MA, United States. 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). 〈10.4230/LIPIcs.WABI.2017.00〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01616499
Contributeur : Maxime Crochemore <>
Soumis le : vendredi 13 octobre 2017 - 17:01:44
Dernière modification le : lundi 16 octobre 2017 - 10:14:05

Fichier

WABI_2017_paper_27.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Maxime Crochemore, Alexandre Francisco, Solon Pissis, Cátia Vaz. Towards distance-based phylogenetic inference in average-case linear-time. International Workshop on Algorithms in Bioinformatics, Aug 2017, Boston, MA, United States. 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). 〈10.4230/LIPIcs.WABI.2017.00〉. 〈hal-01616499〉

Partager

Métriques

Consultations de la notice

4

Téléchargements de fichiers

3