King's College London

Research portal

Towards Distance-Based Phylogenetic Inference in Average-Case Linear-Time

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Maxime Crochemore, Alexandre P. Francisco, Solon P. Pissis, Cátia Vaz

Original languageEnglish
Title of host publication17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
EditorsRussell Schwartz, Knut Reinert
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Pages9:1-9:14
Number of pages14
Volume88
ISBN (Print)978-3-95977-050-7
DOIs
Publication statusPublished - 3 Aug 2017
Event17th International Workshop on Algorithms in Bioinformatics (WABI 2017) - Boston, United States
Duration: 21 Aug 201723 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Conference

Conference17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
CountryUnited States
CityBoston
Period21/08/201723/08/2017

Documents

King's Authors

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 Hamming distance threshold. This article 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 well known phylogenetic inference method.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454