• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Comparative Genomics(RECOMB-CG 2007); 20061201-03; San Diego, CA(US) >How to Achieve an Equivalent Simple Permutation in Linear Time
【24h】

How to Achieve an Equivalent Simple Permutation in Linear Time

机译：如何在线性时间中实现等效的简单置换

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

摘要

The problem of Sorting signed permutations by reversals is a well studied problem in computational biology. The first polynomial time algorithm was presented by Hannenhalli and Pevzner in 1995 [5]. The algorithm was improved several times, and nowadays the most efficient algorithm has a subquadratic running time [9,8]. Simple permutations played an important role in the development of these algorithms. Although the latest result of Tannier et al. [8] does not require simple permutations the preliminary version of their algorithm [9] as well as the first polynomial time algorithm of Hannenhalli and Pevzner [5] use the structure of simple permutations. However, the latter algorithms require a precomputation that transforms a permutation into an equivalent simple permutation. To the best of our knowledge, all published algorithms for this transformation have at least a quadratic running time. For further investigations on genome rearrangement problems, the existence of a fast algorithm for the transformation could be crucial. In this paper, we present a linear time algorithm for the transformation.
机译：通过逆向对有序排列进行排序的问题在计算生物学中是一个经过充分研究的问题。 Hannenhalli和Pevzner在1995年提出了第一个多项式时间算法[5]。该算法进行了数次改进，如今，最有效的算法具有次二次运行时间[9,8]。简单排列在这些算法的开发中起着重要作用。虽然Tannier等人的最新结果。 [8]不需要简单置换他们算法[9]的初步版本以及Hannenhalli和Pevzner [5]的第一个多项式时间算法都使用简单置换的结构。但是，后一种算法需要预计算，该预计算将排列转换为等效的简单排列。据我们所知，所有已发布的用于该变换的算法至少具有二次运行时间。为了进一步研究基因组重排问题，快速的转化算法可能至关重要。在本文中，我们提出了一种用于转换的线性时间算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号