...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Bioinformatics and Computational Biology >A general heuristic for genome rearrangement problems
【24h】

A general heuristic for genome rearrangement problems

机译：基因组重排问题的一般启发式方法

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

摘要

In this paper, we present a general heuristic for several problems in the genome rearrangement field. Our heuristic does not solve any problem directly, it is rather used to improve the solutions provided by any non-optimal algorithm that solve them. Therefore, we have implemented several algorithms described in the literature and several algorithms developed by ourselves. As a whole, we implemented 23 algorithms for 9 well known problems in the genome rearrangement field. A total of 13 algorithms were implemented for problems that use the notions of prefix and suffix operations. In addition, we worked on 5 algorithms for the classic problem of sorting by transposition and we conclude the experiments by presenting results for 3 approximation algorithms for the sorting by reversals and transpositions problem and 2 approximation algorithms for the sorting by reversals problem. Another algorithm with better approximation ratio can be found for the last genome rearrangement problem, but it is purely theoretical with no practical implementation. The algorithms we implemented in addition to our heuristic lead to the best practical results in each case. In particular, we were able to improve results on the sorting by transpositions problem, which is a very special case because many efforts have been made to generate algorithms with good results in practice and some of these algorithms provide results that equal the optimum solutions in many cases. Our source codes and benchmarks are freely available upon request from the authors so that it will be easier to compare new approaches against our results.
机译：在本文中，我们提出了一种基因组重排领域中若干问题的一般启发式方法。我们的启发式方法不能直接解决任何问题，而是用于改进解决问题的任何非最优算法所提供的解决方案。因此，我们已经实现了文献中描述的几种算法以及我们自己开发的几种算法。总体而言，我们针对基因组重排领域中的9个众所周知的问题实施了23种算法。对于使用前缀和后缀运算概念的问题，总共实现了13种算法。此外，我们针对经典的按转位排序问题研究了5种算法，并通过提出3种针对逆转和换位问题进行排序的近似算法和2种针对逆转问题进行排序的近似算法的结果来结束实验。对于最后一个基因组重排问题，可以找到另一种具有更好近似率的算法，但这纯粹是理论上的，没有实际实现。在每种情况下，除了启发式算法外，我们还采用了其他算法，从而可以得出最佳的实际结果。尤其是，我们能够改善按换位排序问题的结果，这是一个非常特殊的情况，因为在实践中已经做出了很多努力来生成具有良好结果的算法，并且其中一些算法提供的结果等于许多情况下的最优解。案件。我们的源代码和基准可应作者的要求免费提供，因此可以更轻松地将新方法与我们的结果进行比较。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号