Maximum parsimony for tree mixtures

Grünewald, Stefan and Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 (2009) Maximum parsimony for tree mixtures. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6 (1). pp. 97-102. ISSN 1545-5963

Full text not available from this repository. (Request a copy)

Abstract

With the number of sequenced genomes growing ever larger, it is now common practice to concatenate sequence alignments from several genomic loci as a first step to phylogenetic tree inference. However, as different loci may support different trees due to processes such as gene duplication and lineage sorting, it is important to better understand how commonly used phylogenetic inference methods behave on such "phylogenetic mixtures". Here we shall focus on how parsimony, one of the most popular methods for reconstructing phylogenetic trees, behaves for mixtures of two trees. In particular, we show that (i) the parsimony problem is NP-complete for mixtures of two trees, (ii) there are mixtures of two trees that have exponentially many (in the number of leaves) most parsimonious trees, and (iii) give an explicit description of the most parsimonious tree(s) and scores corresponding to the mixture of a pair of trees related by a single TBR operation.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018)
Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018)
Faculty of Science > Research Groups > Computational Biology
Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User: Vishal Gautam
Date Deposited: 07 Mar 2011 13:23
Last Modified: 15 Jun 2023 23:51
URI: https://ueaeprints.uea.ac.uk/id/eprint/22428
DOI: 10.1109/TCBB.2008.75

Actions (login required)

View Item View Item