Synthesizing species trees from gene trees using the parameterized and graph-theoretic approaches

dc.contributor.advisor Oliver Eulenstein
dc.contributor.author Moon, Ju Cheol
dc.contributor.department Computer Science
dc.date 2018-08-11T16:22:54.000
dc.date.accessioned 2020-06-30T03:04:57Z
dc.date.available 2020-06-30T03:04:57Z
dc.date.copyright Sun Jan 01 00:00:00 UTC 2017
dc.date.embargo 2001-01-01
dc.date.issued 2017-01-01
dc.description.abstract <p>Gene trees describe how parts of the species have evolved over time, and it is assumed that gene trees have evolved along the branches of the species tree. However, some of gene trees are often discordant with the corresponding species tree due to the complicated evolution history of genes. To overcome this obstacle, median problems have emerged as a major tool for synthesizing species trees by reconciling discordance in a given collection of gene trees. Given a collection of gene trees and a cost function, the median problem seeks a tree, called median tree, that minimizes the overall cost to the gene trees. Median tree problems are typically NP-hard, and there is an increased interest in making such median tree problems available for large-scale species tree construction.</p> <p>In this thesis work, we first show that the gene duplication median tree problem satisfied the weaker version of the Pareto property and propose a parameterized algorithm to solve the gene duplication median tree problem. Second, we design two efficient methods to handle the issues of applying the parameterized algorithm to unrooted gene trees which are sampled from the different species. Third, we introduce the graph-theoretic formulation of the Robinson-Foulds median tree problem and a new tree edit operation. Fourth, we propose a new metric between two phylogenetic trees and examine the statistical properties of the metric. Finally, we propose a new clustering criteria in a bipartite network and propose a new NP-hard problem and its ILP formulation.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/15581/
dc.identifier.articleid 6588
dc.identifier.contextkey 11058079
dc.identifier.doi https://doi.org/10.31274/etd-180810-5198
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/15581
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/29764
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/15581/Moon_iastate_0097E_16613.pdf|||Fri Jan 14 20:43:16 UTC 2022
dc.subject.disciplines Computer Sciences
dc.title Synthesizing species trees from gene trees using the parameterized and graph-theoretic approaches
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
thesis.degree.discipline Computer Science
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 1 of 1
Name:
Moon_iastate_0097E_16613.pdf
Size:
2.78 MB
Format:
Adobe Portable Document Format
Description: