Kernelizations for the hybridization number problem on multiple nonbinary trees
作者:
Highlights:
• We study constructing a network displaying a given collection of phylogenetic trees.
• Our kernelization techniques work for inputs consisting of multiple binary trees.
• Previous results were restricted to two trees and/or binary trees.
• A unified and simplified approach for dealing with common chains of nonbinary trees.
• Polynomial-time solvability with fixed number of reticulations.
摘要
•We study constructing a network displaying a given collection of phylogenetic trees.•Our kernelization techniques work for inputs consisting of multiple binary trees.•Previous results were restricted to two trees and/or binary trees.•A unified and simplified approach for dealing with common chains of nonbinary trees.•Polynomial-time solvability with fixed number of reticulations.
论文关键词:Fixed-parameter tractability,Kernelization,Phylogenetic tree,Phylogenetic network,Hybridization number
论文评审过程:Received 10 July 2014, Revised 5 January 2016, Accepted 15 March 2016, Available online 31 March 2016, Version of Record 10 June 2016.
论文官网地址:https://doi.org/10.1016/j.jcss.2016.03.006