The\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \mathcal{R}^{ + - }}{ \mathcal{F}^{ + - }}$$
\end{document}Consistency problem takes as input two sets\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${R^ + }$$
\end{document}and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${R^ - }$$
\end{document}of resolved triplets and two sets\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${F^ + }$$
\end{document}and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${F^ - }$$
\end{document}of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${R^ + } \cup {F^ + }$$
\end{document}and no elements in\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${R^ - } \cup {F^ - }$$
\end{document}as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${R^ - } = \emptyset$$
\end{document}whose running time is linear in the size of the input and therefore optimal.
Get full access to this article
View all access options for this article.
References
1.
AhoA.V., SagivY., SzymanskiT.G., et al.1981. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput., 10, 405–421.
2.
Bininda-EmondsO.R.P.2004. The evolution of supertrees. Trends Ecol. Evol., 19, 315–322.
3.
Bininda-EmondsO.R.P., CardilloM., JonesK.E., et al.2007. The delayed rise of present-day mammals. Nature, 446, 507–512.
4.
BryantD.1997. Building trees, hunting for trees, and comparing trees: Theory and methods in phylogenetic analysis [Ph.D. thesis]. University of Canterbury, Christchurch, New Zealand.
5.
ByrkaJ., GawrychowskiP., HuberK.T., et al.2010a. Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. J. Discrete Algorithms, 8, 65–75.
6.
ByrkaJ., GuillemotS., and JanssonJ.2010b. New results on optimizing rooted triplets consistency. Discrete Appl. Math., 158, 1136–1147.
7.
ChorB., HendyM., and PennyD.2007. Analytic solutions for three taxon ML trees with variable rates across sites. Discrete Appl. Math., 155, 750–758.
8.
ConstantinescuM., and SankoffD.1995. An efficient algorithm for supertrees. J. Classif., 12, 101–112.
9.
DannenbergK., JanssonJ., LingasA., et al.The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets. In preparation. A Preliminary Version Appeared in the Proceedings of CPM 2015, Volume 9133 of LNCS, pp. 272–283, 2015.
GareyM., and JohnsonD.1979. Computers and Intractability—A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, NY.
12.
GuillemotS., JanssonJ., and SungW.-K.2011. Computing a smallest multilabeled phylogenetic tree from rooted triplets. IEEE/ACM Trans. Comput. Biol. Bioinform., 8, 1141–1147.
13.
HeY.J., HuynhT.N.D., JanssonJ., et al.2006. Inferring phylogenetic relationships avoiding forbidden rooted triplets. J. Bioinform. Comput. Biol., 4, 59–74.
14.
HenzingerM.R., KingV., and WarnowT.1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica, 24, 1–13.
15.
HuberK.T., van IerselL., MoultonV., et al.2017. Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. Algorithmica, 77, 173–200.
16.
JanssonJ., LemenceR.S., and LingasA.2012. The complexity of inferring a minimally resolved phylogenetic supertree. SIAM J. Comput., 41, 272–291.
17.
JanssonJ., NguyenN. B., and SungW.-K.2006. Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J. Comput., 35, 1098–1121.
18.
JanssonJ., and SungW.-K.2016. Minimal phylogenetic supertrees and local consensus trees, 1–53. In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier. Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs, volume 58. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Saarbrücken, Germany.
19.
NgM.P., and WormaldN.C.1996. Reconstruction of rooted trees from subtrees. Discrete Appl. Math., 69, 19–31.
