Linz Simone, Semple Charles
Heinrich-Heine University, Düsseldorf.
IEEE/ACM Trans Comput Biol Bioinform. 2009 Jan-Mar;6(1):30-45. doi: 10.1109/TCBB.2008.86.
Reticulate evolution--the umbrella term for processes like hybridization, horizontal gene transfer, and recombination--plays an important role in the history of life of many species. Although the occurrence of such events is widely accepted, approaches to calculate the extent to which reticulation has influenced evolution are relatively rare. In this paper, we show that the NP-hard problem of calculating the minimum number of reticulation events for two (arbitrary) rooted phylogenetic trees parameterized by this minimum number is fixed-parameter tractable.
网状进化——杂交、水平基因转移和重组等过程的统称——在许多物种的生命史上发挥着重要作用。尽管此类事件的发生已被广泛接受，但计算网状进化对进化影响程度的方法相对较少。在本文中，我们表明，对于以该最小数量为参数的两棵（任意）有根系统发育树，计算最小网状进化事件数量的NP难问题是固定参数可处理的。
