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

dc.contributor.advisor Oliver Eulenstein Moon, Ju Cheol
dc.contributor.department Computer Science 2018-08-11T16:22:54.000 2020-06-30T03:04:57Z 2020-06-30T03:04:57Z Sun Jan 01 00:00:00 UTC 2017 2001-01-01 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/
dc.identifier.articleid 6588
dc.identifier.contextkey 11058079
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/15581
dc.language.iso en
dc.source.bitstream archive/|||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 Computer Science dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
2.78 MB
Adobe Portable Document Format