Contributions to computational phylogenetics and algorithmic self-assembly

dc.contributor.advisor David Fernández-Baca
dc.contributor.author Shutters, Brad
dc.contributor.department Computer Science
dc.date 2018-07-24T08:09:02.000
dc.date.accessioned 2020-06-30T02:47:58Z
dc.date.available 2020-06-30T02:47:58Z
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>This dissertation addresses some of the algorithmic and combinatorial problems at the interface between biology and computation.</p> <p>In particular, it focuses on problems in both computational phylogenetics, an area of study in which computation is used to better understand evolutionary relationships, and algorithmic self-assembly, an area of study in which biological processes are used to perform computation.</p> <p>The first set of results investigate inferring phylogenetic trees from multi-state character data. We give a novel characterization of when a set of three-state characters has a perfect phylogeny and make progress on a long-standing conjecture regarding the compatibility of multi-state characters.</p> <p>The next set of results investigate inferring phylogenetic supertrees from collections of smaller input trees when the input trees do not fully agree on the relative positions of the taxa. Two approaches to dealing with such conflicting input trees are considered. The first is to contract a set of edges in the input trees so that the resulting trees have an agreement supertree. The second is to remove a set of taxa from the input trees so that the resulting trees have an agreement supertree. We give fixed-parameter tractable algorithms for both approaches.</p> <p>We then turn to the algorithmic self-assembly of fractal structures from DNA tiles and investigate approximating the Sierpinski triangle and the Sierpinski carpet with strict self-assembly. We prove tight bounds on approximating the Sierpinski triangle and exhibit a class of fractals that are generalizations of the Sierpinski carpet that can approximately self-assemble.</p> <p>We conclude by discussing some ideas for further research.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/13190/
dc.identifier.articleid 4197
dc.identifier.contextkey 4250846
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/13190
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/27379
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/13190/Shutters_iastate_0097E_13523.pdf|||Fri Jan 14 19:46:31 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.keywords agreement supertrees
dc.subject.keywords algorithmic self-assembly
dc.subject.keywords computational phylogenetics
dc.subject.keywords fractal self-assembly
dc.subject.keywords perfect phylogeny
dc.subject.keywords quartet compatibility
dc.title Contributions to computational phylogenetics and algorithmic self-assembly
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:
Shutters_iastate_0097E_13523.pdf
Size:
1.68 MB
Format:
Adobe Portable Document Format
Description: