A fixed-parameter algorithm for minimum quartet inconsistency

✍ Scribed by Jens Gramm; Rolf Niedermeier

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 285 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00077-1

✦ Synopsis

Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the Minimum Quartet Inconsistency (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet topologies. The more general problem where we are not necessarily given a topology for every subset of four taxa appears to be fixed-parameter intractable. For MQI, however, which is also NP-complete, we can compute the required tree in time Oð4 k n þ n 4 Þ: This means that the problem is fixed-parameter tractable and that in the case of a small number k of ''errors'' the tree reconstruction can be done efficiently. In particular, for minimal k; our algorithm can produce all solutions that resolve k errors. Additionally, we discuss significant heuristic improvements. Experiments underline the practical relevance of our solutions.