• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >Constructing a Gene Team Treein Almost $O$$(n; {rm lg}; n)$ Time
【24h】

Constructing a Gene Team Treein Almost $O$$(n; {rm lg}; n)$ Time

机译：建立一个基因团队树，几乎花费$ O $$（n; {rm lg}; n）$时间

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

摘要

An important model of a conserved gene cluster is called the gene team model, in which a chromosome is defined to be a permutation of distinct genes and a gene team is defined to be a set of genes that appear in two or more species, with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold $delta$. A gene team tree is a succinct way to represent all gene teams for every possible value of $delta$. The previous fastest algorithm for constructing a gene team tree of two chromosomes requires $O(n {rm lg} n ;{rm lglg} n)$ time, which was given by Wang and Lin. Its bottleneck is a problem called the maximum-gap problem. In this paper, by presenting an improved algorithm for the maximum-gap problem, we reduce the upper bound of the gene team tree problem to $O(n {rm lg} n alpha (n))$. Since $alpha$ grows extremely slowly, this result is almost as efficient as the current best upper bound, $O(n {rm lg} n)$, for finding the gene teams of a fixed $delta$ value. Our new algorithm is very efficient from both the theoretical and practical points of view. Wang and Lin's gene-team-tree algorithm can be extended to $k$ chromosomes with complexity $O(kn {rm lg} n {rm lglg} n)$. Similarly, our improved algorithm for the maximum-gap problem reduces this running time to $O(kn {rm lg} n alpha (n))$. In addition, it also provides new upper bounds for the gene team tree problem on general sequences, in which multiple copies of the same gene are allowed.
机译：保守基因簇的重要模型称为基因组模型，其中染色体定义为不同基因的排列，而基因组定义为出现在两个或多个物种中的一组基因，其中团队中每个染色体的相邻基因之间的距离始终不超过某个阈值$ delta $。基因团队树是代表$ delta $每种可能值的所有基因团队的简洁方法。先前构建两个染色体的基因团队树的最快算法需要$ O（n {rm lg} n； {rm lglg} n）$时间，这由Wang和Lin给出。它的瓶颈是一个称为最大间隙问题的问题。在本文中，通过提出一种针对最大间隙问题的改进算法，我们将基因组树问题的上限降低为$ O（n {rm lg} n alpha（n））$。由于$ alpha $的增长极其缓慢，因此该结果几乎与当前的最佳上限$ O（n {rm lg} n）$一样有效，可以找到固定的delta $值的基因团队。从理论和实践的角度来看，我们的新算法都非常有效。 Wang和Lin的基因团队树算法可以扩展到$ k $个具有复杂度$ O（kn {rm lg} n {rm lglg} n）$的染色体。类似地，我们针对最大间隙问题的改进算法将运行时间减少到$ O（kn {rm lg} n alpha（n））$。此外，它还为通用序列中的基因团队树问题提供了新的上限，在通用序列中允许同一基因的多个拷贝。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号