Recently, considerable effort has been put into developing fast algorithms to reconstruct a rooted phylogenetic network that explains two rooted phylogenetic trees and has a minimum number of hybridization vertices. With the standard app1235roach to tackle this problem being combinatorial, the reconstructed network is rarely unique. From a biological point of view, it is therefore of importance to not only compute one network, but all possible networks. In this article, we make a first step toward approaching this goal by presenting the first algorithm—called allMAAFs—that calculates all maximum-acyclic-agreement forests for two rooted binary phylogenetic trees on the same set of taxa.
Get full access to this article
View all access options for this article.
References
1.
AlbrechtB.2011. Fast computation of hybridization networks [MSc thesis]University of Tübingen: Germany.
2.
AlbrechtB., ScornavaccaC., CenciA.et al.2012. Fast computation of minimum hybridization networks. Bioinformatics, 28:191–197.
3.
BaroniM., GrünewaldS., MoultonV.et al.2005. Bounding the number of hybridisation events for a consistent evolutionary history. J. Math. Biol., 51:171–182.
4.
BaroniM., SempleC., SteelM.2006. Hybrids in real time. Syst. Biol., 55:46–56.
5.
BordewichM., SempleC.2007a. Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. IEEE Trans. Comput. Biol. Bioinf., 4:458–466.
6.
BordewichM., SempleC.2007b. Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl. Math., 155:914–928.
7.
ChenZ.Z., WangL.2010. HybridNET: a tool for constructing hybridization networks. Bioinformatics, 26:2912–2913.
8.
CollinsJ., LinzS., SempleC.2011. Quantifying hybridization in realistic time. J. of Comp. Biol., 18:1305–1318.
9.
HusonD.H., ScornavaccaC.2011. A survey of combinatorial methods for phylogenetic networks. Genome Biol. Evol., 3:23–35.
10.
HusonD.H., RichterD.C., RauschC.et al.2007. Dendroscope: An interactive viewer for large phylogenetic trees. BMC Bioinformatics, 8:460.
11.
HusonD.H., RuppR., ScornavaccaC.2011. Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press: New York.
12.
KelkS., van IerselL., LekicN.et al.2012. Cycle killer.. qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set. SIAM J. Discrete Math.in press.
13.
SempleC.2007. Hybridization networks, 277–314. GascuelO., SteelM.Reconstructing Evolution - New Mathematical and Computational Advances. Oxford University Press: New York.
14.
SempleC., SteelM.2003. Phylogenetics. Oxford University Press: New York.
15.
WhiddenC., ZehN.2009. A unifying view on approximation and fpt of agreement forests, 390–402. SalzbergS., WarnowT.Lecture Notes in Computer Science, 5724. Springer: New York.
16.
WhiddenC., BeikoR., ZehN.2010. Fast FPT algorithms for computing rooted agreement forests: Theory and experiments, 141–153. Proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010. Lecture Notes in Computer Science, 6049. Springer: New York.
17.
WhiddenC., BeikoR.G., ZehN.2011. Fixed-parameter and approximation algorithms for maximum agreement forests. http://arxiv.org/abs/1108.2664v1. 2012August.
