2013/07/30 by Sudheer Vakati, Vakati, Sudheer, David Fernández‐Baca +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Bioinformatics and Genomic Networks #Computational Engineering #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Finance #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Quantitative Methods (q-bio.QM) #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.1307.7828
openalex publication_date 2013/07/30 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Deciding whether there is a single tree -a supertree- that summarizes the\nevolutionary information in a collection of unrooted trees is a fundamental\nproblem in phylogenetics. We consider two versions of this question: agreement\nand compatibility. In the first, the supertree is required to reflect precisely\nthe relationships among the species exhibited by the input trees. In the\nsecond, the supertree can be more refined than the input trees.\n Tree compatibility can be characterized in terms of the existence of a\nspecific kind of triangulation in a structure known as the display graph.\nAlternatively, it can be characterized as a chordal graph sandwich problem in a\nstructure known as the edge label intersection graph. Here, we show that the\nlatter characterization yields a natural characterization of compatibility in\nterms of minimal cuts in the display graph, which is closely related to\ncompatibility of splits. We then derive a characterization for agreement.\n