A Simple Fixed Parameter Tractable Algorithm for Computing the Hybridization Number of Two (Not Necessarily Binary) Trees

✍ Scribed by Piovesan, Teresa; Kelk, Steven M.

• Book ID: 126727746
• Publisher: IEEE
• Year: 2013
• Tongue: English
• Weight: 243 KB
• Volume: 10
• Category: Article
• ISSN: 1545-5963
• DOI: 10.1109/TCBB.2012.134

✦ Synopsis

Here, we present a new fixed parameter tractable algorithm to compute the hybridization number r of two rooted, not necessarily binary phylogenetic trees on taxon set X in time ð6 r r!Þ Á polyðnÞ, where n ¼ jXj. The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on X , and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.