Phylogenetic networks are a useful model that can represent reticulate evolution and complex biological data. In recent years, mathematical and computational aspects of tree-based networks have been well studied. However, not all phylogenetic networks are tree-based, so it is meaningful to consider how close a given network is to being tree-based; Francis-Steel-Semple (2018) proposed several different indices to measure the degree of deviation of a phylogenetic network from being tree-based. One is the minimum number of leaves that need to be added to convert a given network to tree-based, and another is the number of vertices that are not included in the largest subtree covering its leaf-set. Both values are zero if and only if the network is tree-based. Both deviation indices can be computed efficiently, but the relationship between the above two is unknown, as each has been studied using different approaches. In this study, we derive a tight inequality for the values of the two measures and also give a characterisation of phylogenetic networks such that they coincide. This characterisation yields a new efficient algorithm for the Maximum Covering Subtree Problem based on the maximal zig-zag trail decomposition.

Tree-based phylogenetic networks provide a powerful model for representing complex data or non-tree-like evolution. Such networks consist of an underlying evolutionary tree called a "support tree" (also known as a "subdivision tree") together with extra arcs added between the edges of that tree. However, a tree-based network can have exponentially many support trees, and this leads to a variety of computational problems. Recently, Hayamizu established a theory called the structure theorem for rooted binary phylogenetic networks and provided linear-time and linear-delay algorithms for different problems, such as counting, optimization, and enumeration of support trees. However, in practice, it is often more useful to search for both optimal and near-optimal solutions than to calculate only an optimal solution. In the present paper, we thus consider the following problem: Given a tree-based phylogenetic network N where each arc is weighted by its probability, compute the ranking of top- k support trees of N according to their likelihood values. We provide a linear-delay (and hence optimal) algorithm for this problem.

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.

The problem of realizing finite metric spaces in terms of weighted graphs has many applications. For example, the mathematical and computational properties of metrics that can be realized by trees have been well-studied and such research has laid the foundation of the reconstruction of phylogenetic trees from evolutionary distances. However, as trees may be too restrictive to accurately represent real-world data or phenomena, it is important to understand the relationship between more general graphs and distances. In this paper, we introduce a new type of metric called a cactus metric, that is, a metric that can be realized by a cactus graph. We show that, just as with tree metrics, a cactus metric has a unique optimal realization. In addition, we describe an algorithm that can recognize whether or not a metric is a cactus metric and, if so, compute its optimal realization in O(n3) time, where n is the number of points in the space.

We attempt to shed new light on the notion of ‘tree-like’ metric spaces by focusing on an approach that does not use the four-point condition. Our key question is: Given metric space M on n points, when does a fully labelled positive-weighted tree T exist on the same n vertices that precisely realises M using its shortest path metric? We prove that if a spanning tree representation, T , of M exists, then it is isomorphic to the unique minimum spanning tree in the weighted complete graph associated with M , and we introduce a fourth-point condition that is necessary and sufficient to ensure the existence of T whenever each distance in M is unique. In other words, a finite median graph, in which each geodesic distance is distinct, is simply a tree. Provided that the tie-breaking assumption holds, the fourth-point condition serves as a criterion for measuring the goodness-of-fit of the minimum spanning tree to M , i.e., the spanning tree-likeness of M . It is also possible to evaluate the spanning path-likeness of M . These quantities can be measured in O ( n 4 ) and O ( n 3 ) time, respectively.

Recent years have witnessed a surge of biological interest in the minimum spanning tree (MST) problem for its relevance to automatic model construction using the distances between data points. Despite the increasing use of MST algorithms for this purpose, the goodness-of-fit of an MST to the data is often elusive because no quantitative criteria have been developed to measure it. Motivated by this, we provide a necessary and sufficient condition to ensure that a metric space on n points can be represented by a fully labeled tree on n vertices, and thereby determine when an MST preserves all pairwise distances between points in a finite metric space.