Idioma:

A fixed-parameter algorithm for minimum quartet inconsistency

Gramm, Jens ; Niedermeier, Rolf

Journal of computer and system sciences, 2003-12, Vol.67 (4), p.723-741 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
A fixed-parameter algorithm for minimum quartet inconsistency
Autor: Gramm, Jens ; Niedermeier, Rolf
Assuntos: Computational biology ; Minimum quartet inconsistency ; Parameterized complexity ; Phylogeny ; Quartet methods
É parte de: Journal of computer and system sciences, 2003-12, Vol.67 (4), p.723-741
Descrição: Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the M inimum Q uartet I nconsistency (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.
Editor: Elsevier Inc
Idioma: Inglês

Voltar para lista de resultados