A STRUCTURE THEOREM FOR ROOTED BINARY PHYLOGENETIC NETWORKS AND ITS IMPLICATIONS FOR TREE-BASED NETWORKS

Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis. In the last few years, therefore, "tree-based"phylogenetic networks, which are defined by a spanning tree called a "subdivision tree"that is an embedding of a phylogenetic tree on the same leaf-set, have attracted the attention of many theoretical biologists. However, the application of such networks is still not easy, due to many important computational problems whose time complexities are unknown or not clearly understood. In this paper, we provide a general framework for solving those various old or new problems on tree-based phylogenetic networks from a coherent perspective, rather than analyzing the complexity of each individual problem or developing an algorithm one by one. More precisely, we establish a structure theorem that gives a way to canonically decompose any rooted binary phylogenetic network N into maximal zig-zag trails that are uniquely determined by N, and furthermore use it to characterize the set of subdivision trees of N in the form of a direct product. From these main results, we derive a series of linear time (and linear time delay) algorithms for solving the following problems: given a rooted binary phylogenetic network N, (1) determine whether or not N has a subdivision tree and find one if there exists any (decision/search problems); (2) measure the deviation of N from being tree-based (deviation quantification problem); (3) compute the number of subdivision trees of N (counting problem); (4) list all subdivision trees of N (enumeration problem); and (5) find a subdivision tree to maximize or minimize a prescribed objective function (optimization problem). All algorithms proposed here are optimal in terms of time complexity. Our results not only imply and unify various known results in the relevant literature, but also answer many open questions and moreover enable novel applications, such as the estimation of a maximum likelihood tree underlying a tree-based network. The results and algorithms in this paper also apply for a special class of rooted nonbinary phylogenetic networks.