Fixed parameter algorithms for compatible and agreement supertree problems

dc.contributor.advisor David Fernandez-Baca Vakati, Sudheer
dc.contributor.department Computer Science 2018-07-23T12:20:35.000 2020-06-30T02:48:19Z 2020-06-30T02:48:19Z Tue Jan 01 00:00:00 UTC 2013 2015-07-30 2013-01-01
dc.description.abstract <p>Biologists represent evolutionary history of species through phylogenetic trees. Leaves of a phylogenetic tree represent the species and internal vertices represent the extinct ancestors. Given a collection of input phylogenetic trees, a common problem in computational biology is to build a supertree that captures the evolutionary history of all the species in the input trees, and is consistent with each of the input trees. In this document we study the tree compatibility and agreement supertree problems.</p> <p>Tree compatibility problem is NP-complete but has been shown to be fixed parameter tractable when parametrized by number of input trees. We characterize the compatible supertree problem in terms of triangulation of a structure called the display graph. We also give an alternative characterization in terms of cuts of the display graph. We show how these characterizations are related to characterization given in terms of triangulation of the edge label intersection graph. We then give a characterization of the agreement supertree problem.</p> <p>In real world data, consistent supertrees do not always exist. Inconsistencies can be dealt with by contraction of edges or removal of taxa. The agreement supertree edge contraction (AST-EC) problem asks if a collection of k rooted trees can be made to agree by contraction of at most p edges. Similarly, the agreement supertree taxon removal (AST-TR) problem asks if a collection of k rooted trees can be made to agree by removal of at most p taxa. We give fixed parameter algorithms for both cases when parametrized by k and p.</p> <p>We study the long standing conjecture on the perfect phylogeny problem; there exists a function f (r) such that a given collection C of r-state characters is compatible if and only if every f (r) subset of C is compatible. We will show that for r ≥ 2, f (r) ≥ lceil (r/2) rceil * lfloor(r/2)rfloor + 1.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 4245
dc.identifier.contextkey 4615730
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/13238
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 19:47:58 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.keywords Agreement supertrees
dc.subject.keywords Character Compatibility
dc.subject.keywords Display graphs
dc.subject.keywords Graph Triangulations
dc.subject.keywords Phylogenetics
dc.subject.keywords Tree Compatibility
dc.title Fixed parameter algorithms for compatible and agreement supertree problems
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456 dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
759.25 KB
Adobe Portable Document Format