Towards distance-based phylogenetic inference in average-case linear-time - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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

Maxime Crochemore
Alexandre P Francisco
  • Fonction : Auteur
Cátia Vaz
  • Fonction : Auteur

Résumé

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.
Fichier principal
Vignette du fichier
WABI_2017_paper_27.pdf (1.44 Mo) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01616499 , version 1 (13-10-2017)

Identifiants

Citer

Maxime Crochemore, Alexandre P Francisco, Solon P 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. ⟨10.4230/LIPIcs.WABI.2017.00⟩. ⟨hal-01616499⟩
27 Consultations
123 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More