• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Synthesizing Species Trees From Gene Trees Using the Parameterized and Graph-Theoretic Approaches
【24h】

Synthesizing Species Trees From Gene Trees Using the Parameterized and Graph-Theoretic Approaches

机译：使用参数化和图论方法从基因树合成物种树

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.;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.
机译：基因树描述了物种的某些部分随时间演变的方式，并假设基因树沿物种树的分支进化。然而，由于基因的复杂进化历史，某些基因树常常与相应的物种树不一致。为了克服这一障碍，正中问题已成为通过协调给定基因树集合中的不一致性来合成物种树的主要工具。给定基因树的集合和成本函数，中位数问题寻求一种称为中位数树的树，该树将基因树的总体成本降至最低。中位数树问题通常是NP难解的，人们越来越有兴趣将此类中位数树问题用于大规模树种构建。；在本文中，我们首先证明基因重复中位数树问题满足较弱版本的帕累托性质，并提出了一种参数化算法来解决基因重复中值树问题。其次，我们设计了两种有效的方法来处理将参数化算法应用于从不同物种中采样的无根基因树的问题。第三，我们介绍了Robinson-Foulds中树问题的图论公式和新的树编辑操作。第四，我们提出了两个系统发育树之间的新指标，并研究了该指标的统计特性。最后，我们在二分网络中提出了一个新的聚类准则，并提出了一个新的NP难题及其ILP公式。

著录项

  • 作者

    Moon, Ju Cheol.;

  • 作者单位

    Iowa State University.;

  • 授予单位 Iowa State University.;
  • 学科 Computer science.
  • 学位 Ph.D.
  • 年度 2017
  • 页码 121 p.
  • 总页数 121
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号