Fast computation of all maximum acyclic agreement forests for two rooted binary phylogenetic trees
Evolutionary scenarios displaying reticulation events are often represented by rooted phylogenetic networks. Due to biological reasons, those events occur very rarely, and, thus, networks containing a minimum number of such events, so-called minimum hybridization networks, are of particular interest for research. Moreover, to study reticulate evolution, biologist need not only a subset but all of those networks. To achieve this goal, the less complex concept of rooted phylogenetic trees can be used as building block. Here, as a first important step, the trees are disjoint into common parts, so-called maximum acyclic agreement forests, which can then be turned into minimum hybridization networks by applying further network building algorithms. In this paper, we present two modifications of the first non-naive algorithm --- called allMAAFs --- computing all maximum acyclic agreement forests for two rooted binary phylogenetic trees on the same set of taxa. By a simulation study, we indicate that through these modifications the algorithm is on average 8 times faster than the original algorithm making this algorithm accessible to larger input trees and, thus, to a wider range of biological problems.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
Computing Hybridization Networks for Multiple Rooted Binary Phylogenetic Trees by Maximum Acyclic Agreement Forests
It is a known fact that, given two rooted binary phylogenetic trees, the concept of maximum acyclic agreement forests is sufficient to compute hybridization networks with minimum hybridization number. In this work, we de…
Computing a Relevant Set of Nonbinary Maximum Acyclic Agreement Forests
There exist several methods dealing with the reconstruction of rooted phylogenetic networks explaining different evolutionary histories given by rooted binary phylogenetic trees. In practice, however, due to insufficient…
An Algebraic Formalization of Forward and Forward-backward Algorithms
In this paper, we propose an algebraic formalization of the two important classes of dynamic programming algorithms called forward and forward-backward algorithms. They are generalized extensively in this study so that a…
SLA Violation Prediction In Cloud Computing: A Machine Learning Perspective
Service level agreement (SLA) is an essential part of cloud systems to ensure maximum availability of services for customers. With a violation of SLA, the provider has to pay penalties. In this paper, we explore two mach…
BIG-bench Machine LearningCloud ComputingGeneral ClassificationMondrian Forests: Efficient Online Random Forests
Ensembles of randomized decision trees, usually referred to as random forests, are widely used for classification and regression tasks in machine learning and statistics. Random forests achieve competitive predictive per…