An Ω( n 2 / log n ) speed-up of TBR heuristics for the gene-duplication problem
作者： Mukul S. Bansal , Oliver Eulenstein
DOI: 10.1007/978-3-540-74126-8_12
关键词:
摘要: The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of duplications. This NP-hard and thus requires efficient effective heuristics. Existing heuristics perform stepwise search the tree space, where each step guided an exact solution instance local problem. We improve on time complexity factor n2/ log n, n size resulting supertree. Typically, several thousand instances solved throughout heuristic search. Hence, our improvement makes much more tractable for large-scale phylogenetic analyses.
springer.com
sci-hub.st 参考文章(28)
James A. Cotton, Roderic D. M. Page, Tangled Tales from Multiple Markers Springer, Dordrecht. pp. 107- 125 ,(2004) , 10.1007/978-1-4020-2330-9_6
Mukul S. Bansal, J. Gordon Burleigh, Oliver Eulenstein, André Wehe, Heuristics for the gene-duplication problem: a Θ(n) speed-up for the local search research in computational molecular biology. pp. 238- 252 ,(2007) , 10.1007/978-3-540-71681-5_17
Oliver Eulenstein, J. Gordon Burleigh, David Fernández-Baca, Duhong Chen, Improved Heuristics for Minimum-Flip Supertree Construction Evolutionary Bioinformatics. ,vol. 2, pp. 0- 0 ,(2006) , 10.4137/EBO.S0
Ulrike Stege, Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable workshop on algorithms and data structures. ,vol. 319, pp. 288- 293 ,(1999) , 10.1007/3-540-48447-7_29
Michael Fellows, Michael Hallett, Ulrike Stege, Analogs & duals of the MAST problem for sequences & trees Journal of Algorithms. ,vol. 49, pp. 192- 216 ,(2003) , 10.1016/S0196-6774(03)00081-6
Bin Ma, Ming Li, Louxin Zhang, On reconstructing species trees from gene trees in term of duplications and losses research in computational molecular biology. pp. 182- 191 ,(1998) , 10.1145/279069.279113
LOUXIN ZHANG, On a Mirkin-Muchnik-Smith conjecture for comparing molecular phylogenies. Journal of Computational Biology. ,vol. 4, pp. 177- 187 ,(1997) , 10.1089/CMB.1997.4.177
Magnus Bordewich, Charles Semple, On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combinatorics. ,vol. 8, pp. 409- 423 ,(2005) , 10.1007/S00026-004-0229-Z
M. T. Hallett, J. Lagergren, New algorithms for the duplication-loss model research in computational molecular biology. pp. 138- 146 ,(2000) , 10.1145/332306.332359
Roderic D.M. Page, Extracting species trees from complex gene trees: reconciled trees and vertebrate phylogeny. Molecular Phylogenetics and Evolution. ,vol. 14, pp. 89- 106 ,(2000) , 10.1006/MPEV.1999.0676