Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees. Böcker, S., Bui, Q. B. A., & Truss, A. ACM Trans Algorithms, 8(1):17 pages, 2012. Article~7doi abstract bibtex In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this paper we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, and we want to find a perfect phylogeny for this matrix using a minimum number of flips, that is, corrections of single entries in the matrix. The graph-theoretical formulation of the problem is as follows: Given a bipartite graph G = (V_t ∪ V_c , E), the task is to find a minimum set of edge modifications such that the resulting graph has no induced path with four edges that starts and ends in V_t , where V_t corresponds to the taxa set and Vc corresponds to the character set. We present two fixed-parameter algorithms for the Minimum-Flip Problem, one with running time O(4.83^k + poly(m, n)) and another one with running time O(4.42^k + poly(m, n)) for n taxa, m characters, k flips, and poly(m, n) denotes a polynomial function in m and n. Additionally, we discuss several heuristic improvements. We also report computational results on phylogenetic data.
@Article{boecker12improved,
author = {Sebastian B\"ocker and Quang Bao Anh Bui and Anke Truss},
title = {Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees},
journal = {ACM Trans Algorithms},
year = {2012},
volume = {8},
number = {1},
pages = {17 pages},
note = {Article~7},
abstract = {In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this paper we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, and we want to find a perfect phylogeny for this matrix using a minimum number of flips, that is, corrections of single entries in the matrix. The graph-theoretical formulation of the problem is as follows: Given a bipartite graph G = (V_t \cup V_c , E), the task is to find a minimum set of edge modifications such that the resulting graph has no induced path with four edges that starts and ends in V_t , where V_t corresponds to the taxa set and Vc corresponds to the character set. We present two fixed-parameter algorithms for the Minimum-Flip Problem, one with running time O(4.83^k + poly(m, n)) and another one with running time O(4.42^k + poly(m, n)) for n taxa, m characters, k flips, and poly(m, n) denotes a polynomial function in m and n. Additionally, we discuss several heuristic improvements. We also report computational results on phylogenetic data.},
doi = {10.1145/2071379.2071386},
file = {BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:2012/BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:PDF},
keywords = {jena; FPT; linkpdf; PABI},
optmonth = jan,
owner = {baoanh},
timestamp = {2009.06.02},
}
Downloads: 0
{"_id":"8Mfwm3aLSwL97AGMP","bibbaseid":"bcker-bui-truss-improvedfixedparameteralgorithmsforminimumflipconsensustrees-2012","authorIDs":[],"author_short":["Böcker, S.","Bui, Q. B. A.","Truss, A."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Sebastian"],"propositions":[],"lastnames":["Böcker"],"suffixes":[]},{"firstnames":["Quang","Bao","Anh"],"propositions":[],"lastnames":["Bui"],"suffixes":[]},{"firstnames":["Anke"],"propositions":[],"lastnames":["Truss"],"suffixes":[]}],"title":"Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees","journal":"ACM Trans Algorithms","year":"2012","volume":"8","number":"1","pages":"17 pages","note":"Article~7","abstract":"In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this paper we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, and we want to find a perfect phylogeny for this matrix using a minimum number of flips, that is, corrections of single entries in the matrix. The graph-theoretical formulation of the problem is as follows: Given a bipartite graph G = (V_t ∪ V_c , E), the task is to find a minimum set of edge modifications such that the resulting graph has no induced path with four edges that starts and ends in V_t , where V_t corresponds to the taxa set and Vc corresponds to the character set. We present two fixed-parameter algorithms for the Minimum-Flip Problem, one with running time O(4.83^k + poly(m, n)) and another one with running time O(4.42^k + poly(m, n)) for n taxa, m characters, k flips, and poly(m, n) denotes a polynomial function in m and n. Additionally, we discuss several heuristic improvements. We also report computational results on phylogenetic data.","doi":"10.1145/2071379.2071386","file":"BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:2012/BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:PDF","keywords":"jena; FPT; linkpdf; PABI","optmonth":"January","owner":"baoanh","timestamp":"2009.06.02","bibtex":"@Article{boecker12improved,\n author = {Sebastian B\\\"ocker and Quang Bao Anh Bui and Anke Truss},\n title = {Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees},\n journal = {ACM Trans Algorithms},\n year = {2012},\n volume = {8},\n number = {1},\n pages = {17 pages},\n note = {Article~7},\n abstract = {In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this paper we study the Minimum-Flip Problem: the input trees are transformed into a binary matrix, and we want to find a perfect phylogeny for this matrix using a minimum number of flips, that is, corrections of single entries in the matrix. The graph-theoretical formulation of the problem is as follows: Given a bipartite graph G = (V_t \\cup V_c , E), the task is to find a minimum set of edge modifications such that the resulting graph has no induced path with four edges that starts and ends in V_t , where V_t corresponds to the taxa set and Vc corresponds to the character set. We present two fixed-parameter algorithms for the Minimum-Flip Problem, one with running time O(4.83^k + poly(m, n)) and another one with running time O(4.42^k + poly(m, n)) for n taxa, m characters, k flips, and poly(m, n) denotes a polynomial function in m and n. Additionally, we discuss several heuristic improvements. We also report computational results on phylogenetic data.},\n doi = {10.1145/2071379.2071386},\n file = {BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:2012/BoeckerEtAl_ImprovedFixedParameterAlgorithms_TALG_2012_preprint.pdf:PDF},\n keywords = {jena; FPT; linkpdf; PABI},\n optmonth = jan,\n owner = {baoanh},\n timestamp = {2009.06.02},\n}\n\n","author_short":["Böcker, S.","Bui, Q. B. A.","Truss, A."],"key":"boecker12improved","id":"boecker12improved","bibbaseid":"bcker-bui-truss-improvedfixedparameteralgorithmsforminimumflipconsensustrees-2012","role":"author","urls":{},"keyword":["jena; FPT; linkpdf; PABI"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.066Z","downloads":0,"keywords":["jena; fpt; linkpdf; pabi"],"search_terms":["improved","fixed","parameter","algorithms","minimum","flip","consensus","trees","böcker","bui","truss"],"title":"Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}