Reconstructing semi-directed level-1 networks using few quarnets
Martin Frohn (Universiteit Maastricht)
N.A.L. Holtgrefe (TU Delft - Discrete Mathematics and Optimization)
Leo van Van Iersel (TU Delft - Discrete Mathematics and Optimization)
M.E.L. Jones (TU Delft - Discrete Mathematics and Optimization)
Steven Kelk (Universiteit Maastricht)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstructs binary n-leaf semi-directed level-1 networks in O(n
2) time from its quarnets (4-leaf subnetworks). Our method assumes we have direct access to all quarnets, yet uses only an asymptotically optimal number of O(nlogn) quarnets. When the network is assumed to contain no triangles, our method instead relies only on four-cycle quarnets and the splits of the other quarnets. A variant of our algorithm works with quartets rather than quarnets and we show that it reconstructs most of a semi-directed level-1 network from an asymptotically optimal O(nlogn) of the quartets it displays. Additionally, we provide an O(n
3) time algorithm that reconstructs the tree-of-blobs of any binary n-leaf semi-directed network with unbounded level from O(n
3) splits of its quarnets.
help_outline