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

Maxime Crochemore 1 Alexandre Francisco Solon Pissis 2 Cátia Vaz
1 Informatics
2 Department of Informatics [King's College London]
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.
Keywords : F22 Nonnumerical Algorithms and computational biology phylogenetic inference Hamming distance
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 : jeudi 19 avril 2018 - 14:24:03
Document(s) archivé(s) le : dimanche 14 janvier 2018 - 13:57:24

Fichier

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

Identifiants

Collections

UPEC-UPEM

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

20

Téléchargements de fichiers

23

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD