2017/07/12 by Steven Kelk, Fabio Pardi, Kelk, Steven +5
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Earth and Planetary Sciences · #Data Structures and Algorithms (cs.DS) #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Plant Diversity and Evolution #Populations and Evolution (q-bio.PE)
paper · pdf · doi:10.48550/arxiv.1707.03648
openalex publication_date 2017/07/12 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Phylogenetic networks are often constructed by merging multiple conflicting\nphylogenetic signals into a directed acyclic graph. It is interesting to\nexplore whether a network constructed in this way induces biologically-relevant\nphylogenetic signals that were not present in the input. Here we show that,\ngiven a multiple alignment A for a set of taxa X and a rooted phylogenetic\nnetwork N whose leaves are labelled by X, it is NP-hard to locate the most\nparsimonious phylogenetic tree displayed by N (with respect to A) even when the\nlevel of N - the maximum number of reticulation nodes within a biconnected\ncomponent - is 1 and A contains only 2 distinct states. (If, additionally, gaps\nare allowed the problem becomes APX-hard.) We also show that under the same\nconditions, and assuming a simple binary symmetric model of character\nevolution, finding the most likely tree displayed by the network is NP-hard.\nThese negative results contrast with earlier work on parsimony in which it is\nshown that if A consists of a single column the problem is fixed parameter\ntractable in the level. We conclude with a discussion of why, despite the\nNP-hardness, both the parsimony and likelihood problem can likely be\nwell-solved in practice.\n