Reconstructing semi-directed level-1 networks using few quarnets
Martin Frohn, Niels Holtgrefe, Leo van Iersel, Mark M. Jones, Steven M. Kelk · Journal of Computer and System Sciences · 2025
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 ( n log n ) 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 ( n log n ) 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.