Analyzing and reconstructing reticulation networks under timing constraints |
| |
Authors: | Simone Linz Charles Semple Tanja Stadler |
| |
Institution: | 1. Department of Computer Science, University of California, Davis, CA, USA 2. Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand 3. Institute of Integrative Biology, ETH Zürich, Zürich, Switzerland
|
| |
Abstract: | Reticulation networks are now frequently used to model the history of life for various groups of species whose evolutionary
past is likely to include reticulation events such as horizontal gene transfer or hybridization. However, the reconstructed
networks are rarely guaranteed to be temporal. If a reticulation network is temporal, then it satisfies the two biologically
motivated timing constraints of instantaneously occurring reticulation events and successively occurring speciation events.
On the other hand, if a reticulation network is not temporal, it is always possible to make it temporal by adding a number
of additional unsampled or extinct taxa. In the first half of the paper, we show that deciding whether a given number of additional
taxa is sufficient to transform a non-temporal reticulation network into a temporal one is an NP-complete problem. As one
is often given a set of gene trees instead of a network in the context of hybridization, this motivates the second half of
the paper which provides an algorithm, called TemporalHybrid, for reconstructing a temporal hybridization network that simultaneously explains the ancestral history of two trees or indicates
that no such network exists. We further derive two methods to decide whether or not a temporal hybridization network exists
for two given trees and illustrate one of the methods on a grass data set. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|