Characterizing Compatibility and Agreement of Unrooted Trees via Cuts in Graphs

详细信息    查看全文

• 作者：Sudheer Vakati (21)
  David Fernández-Baca (21)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8126
• 期：1
• 页码：200-214
• 全文大小：266KB
• 参考文献：1. Aho, A., Sagiv, Y., Szymanski, T., Ullman, J.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput.?10(3), 405-21 (1981) CrossRef
  2. Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms?12(2), 308-40 (1991) CrossRef
  3. Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput.?31(1), 212-32 (2001) CrossRef
  4. Bryant, D., Lagergren, J.: Compatibility of unrooted phylogenetic trees is FPT. Theor. Comput. Sci.?351, 296-02 (2006) CrossRef
  5. Buneman, P.: The recovery of trees from measures of dissimilarity. In: Mathematics in the Archaeological and Historical Sciences, pp. 387-95. Edinburgh University Press, Edinburgh (1971)
  6. Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput.?85(1), 12-5 (1990) CrossRef
  7. Gordon, A.D.: Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labelled leaves. Journal of Classification?9, 335-48 (1986) CrossRef
  8. Gusfield, D.: The multi-state perfect phylogeny problem with missing and removable data: Solutions via integer-programming and chordal graph theory. J. Comput. Biol.?17(3), 383-99 (2010) CrossRef
  9. Gysel, R., Stevens, K., Gusfield, D.: Reducing problems in unrooted tree compatibility to restricted triangulations of intersection graphs. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol.?7534, pp. 93-05. Springer, Heidelberg (2012) CrossRef
  10. Heggernes, P.: Minimal triangulations of graphs: A survey. Discrete Math.?306(3), 297 (2006) CrossRef
  11. Ng, M.P., Wormald, N.C.: Reconstruction of rooted trees from subtrees. Discrete Applied Mathematics?69(1-2), 19-1 (1996) CrossRef
  12. Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math.?79(1-3), 171-88 (1997) CrossRef
  13. Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics. Oxford University Press, Oxford (2003)
  14. Steel, M.A.: The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif.?9, 91-16 (1992) CrossRef
  15. Vakati, S., Fernández-Baca, D.: Graph triangulations and the compatibility of unrooted phylogenetic trees. Appl. Math. Lett.?24(5), 719-23 (2011) CrossRef
  
• 作者单位：Sudheer Vakati (21)
  David Fernández-Baca (21)
  
  21. Department of Computer Science, Iowa State University, Ames, IA, 50011, USA
  

文摘

Deciding whether there is a single tree —a supertree-that summarizes the evolutionary information in a collection of unrooted trees is a fundamental problem in phylogenetics. We consider two versions of this question: agreement and compatibility. In the first, the supertree is required to reflect precisely the relationships among the species exhibited by the input trees. In the second, the supertree can be more refined than the input trees. Tree compatibility can be characterized in terms of the existence of a specific kind of triangulation in a structure known as the display graph. Alternatively, it can be characterized as a chordal graph sandwich problem in a structure known as the edge label intersection graph. Here, we show that the latter characterization yields a natural characterization of compatibility in terms of minimal cuts in the display graph, which is closely related to compatibility of splits. We then derive a characterization for agreement.