Fixed parameter algorithms for compatible and agreement supertree problems

dc.contributor.advisor David Fernandez-Baca
dc.contributor.author Vakati, Sudheer
dc.contributor.department Computer Science
dc.date 2018-07-23T12:20:35.000
dc.date.accessioned 2020-06-30T02:48:19Z
dc.date.available 2020-06-30T02:48:19Z
dc.date.copyright Tue Jan 01 00:00:00 UTC 2013
dc.date.embargo 2015-07-30
dc.date.issued 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/lib.dr.iastate.edu/etd/13238/
dc.identifier.articleid 4245
dc.identifier.contextkey 4615730
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/13238
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/27427
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/13238/Vakati_iastate_0097E_13568.pdf|||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
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
Name:
Vakati_iastate_0097E_13568.pdf
Size:
759.25 KB
Format:
Adobe Portable Document Format
Description: