A new recombination lower bound and the minimum perfect phylogenetic forest problem

DOI10.1007/s10878-007-9129-6zbMath1260.92094OpenAlexW2594198741MaRDI QIDQ1029702

Dan Gusfield, Yu-Feng Wu

Publication date: 13 July 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9129-6

zbMATH Keywords

computational complexitypopulation geneticsancestral recombination graphlower bound on the minimum number of recombination

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Applications of mathematical programming (90C90) Integer programming (90C10) Complexity and performance of numerical algorithms (65Y20)

Related Items (2)

Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ When two trees go to war

Cites Work

• Unnamed Item
• An efficiently computed lower bound on the number of recombinations in phylogenetic networks: theory and empirical study
• The Steiner problem in phylogeny is NP-complete
• On the computational complexity of the rooted subtree prune and regraft distance
• Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations
• Efficient algorithms for inferring evolutionary trees

This page was built for publication: A new recombination lower bound and the minimum perfect phylogenetic forest problem