On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems

Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network

Phylogenetic trees are unable to represent the evolutionary process for a collection of species if reticulation events happened, and a generalized model named phylogenetic network was introduced consequently. However, the representation of the evolutionary process for one gene is actually a phylogenetic tree that is "contained" in the phylogenetic network for the considered species containing the gene. Thus a fundamental computational problem named Tree Containment problem arises, which asks whether a phylogenetic tree is contained in a phylogenetic network. The previous research on the problem mainly focused on its rooted version of which the considered tree and network are rooted, and several algorithms were proposed when the considered network is binary or structure-restricted. There is almost no algorithm for its unrooted version except the recent fixed-parameter algorithm with runtime O(4^kn²), where k and n are the reticulation number and size of the considered unrooted binary phylogenetic network N, respectively. As the runtime is a little expensive when considering big values of k, we aim to improve it and successfully propose a fixed-parameter algorithm with runtime O(2.594^kn²) in the paper. Additionally, we experimentally show its effectiveness on biological data and simulated data.

Estimating Bifurcating Consensus Phylogenetic Trees Using Evolutionary Imperialist Competitive Algorithm

Background:

One of the important goals of phylogenetic studies is the estimation of species-level phylogeny. A phylogenetic tree is an evolutionary classification of different species of creatures. There are several methods to generate such trees, where each method may produce a number of different trees for the species. By choosing the same proteins of all species, it is possible that the topology and arrangement of trees would be different.

Objective:

There are methods by which biologists summarize different phylogenetic trees to a tree, called consensus tree. A consensus method deals with the combination of gene trees to estimate a species tree. As the phylogenetic trees grow and their number is increased, estimating a consensus tree based on the species-level phylogenetic trees becomes a challenge.

Methods:

The current study aims at using the Imperialist Competitive Algorithm (ICA) to estimate bifurcating consensus trees. Evolutionary algorithms like ICA are suitable to resolve problems with the large space of candidate solutions.

Results:

The obtained consensus tree has more similarity to the native phylogenetic tree than related studies.

Conclusion:

The proposed method enjoys mechanisms and policies that enable us more than other evolutionary algorithms in tuning the proposed algorithm. Thanks to these policies and the mechanisms, the algorithm enjoyed efficiently in obtaining the optimum consensus tree. The algorithm increased the possibility of selecting an optimum solution by imposing some changes in its parameters.

Frin: An Efficient Method for Representing Genome Evolutionary History

Phylogenetic analysis is important in understanding the process of biological evolution, and phylogenetic trees are used to represent the evolutionary history. Each taxon in a phylogenetic tree has not more than one parent, so phylogenetic trees cannot express the complex evolutionary information implicit in phylogeny. Phylogenetic networks can be used to express genome evolutionary histories. Therefore, it is great significance to research the construction of phylogenetic networks. Cass algorithm is an efficient method for constructing phylogenetic networks because it can construct a much simpler network. However, Cass relies heavily on the order of input data, i.e. different networks can be constructed for the same dataset with different input orders. Based on the frequency and incompatibility degree of taxa, we propose an efficiently improved algorithm of Cass, called as Frin. The experimental results show that the networks constructed by Frin are not only simpler than those constructed by other methods, but Frin can also construct more consistent phylogenetic networks when the treated data have different input orders. Furthermore, the phylogenetic network constructed by Frin is closer to the original information described by phylogenetic trees. Frin has been built as a Java software package and is freely available at https://github.com/wangjuanimu/Frin.

Tree-Based Unrooted Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that are used to represent non-tree-like evolutionary histories that arise in organisms such as plants and bacteria, or uncertainty in evolutionary histories. An unrooted phylogenetic network on a non-empty, finite set X of taxa, or network, is a connected, simple graph in which every vertex has degree 1 or 3 and whose leaf set is X. It is called a phylogenetic tree if the underlying graph is a tree. In this paper we consider properties of tree-based networks, that is, networks that can be constructed by adding edges into a phylogenetic tree. We show that although they have some properties in common with their rooted analogues which have recently drawn much attention in the literature, they have some striking differences in terms of both their structural and computational properties. We expect that our results could eventually have applications to, for example, detecting horizontal gene transfer or hybridization which are important factors in the evolution of many organisms.

On the fixed parameter tractability of agreement-based phylogenetic distances

Three important and related measures for summarizing the dissimilarity in phylogenetic trees are the minimum number of hybridization events required to fit two phylogenetic trees onto a single phylogenetic network (the hybridization number), the (rooted) subtree prune and regraft distance (the rSPR distance) and the tree bisection and reconnection distance (the TBR distance) between two phylogenetic trees. The respective problems of computing these measures are known to be NP-hard, but also fixed-parameter tractable in their respective natural parameters. This means that, while they are hard to compute in general, for cases in which a parameter (here the hybridization number and rSPR/TBR distance, respectively) is small, the problem can be solved efficiently even for large input trees. Here, we present new analyses showing that the use of the "cluster reduction" rule-already defined for the hybridization number and the rSPR distance and introduced here for the TBR distance-can transform any [Formula: see text]-time algorithm for any of these problems into an [Formula: see text]-time one, where n is the number of leaves of the phylogenetic trees, p is the natural parameter and k is a much stronger (that is, smaller) parameter: the minimum level of a phylogenetic network displaying both trees.