...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Expert Systems with Application >A hybrid crow search algorithm for solving the DNA fragment assembly problem
【24h】

A hybrid crow search algorithm for solving the DNA fragment assembly problem

机译：解决DNA片段装配问题的混合乌鸦搜索算法

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

摘要

The sequencing of DNA goes through a step of fragment assembly, this step is known as DNA fragment assembly problem (FAP). Fragment assembly is considered as an NP-hard problem, which means there is no known polynomial-time exact approach, hence the need for meta-heuristics. Three major strategies are widely used to tackle this problem: greedy graph-based algorithms, de Bruijn graphs, and the overlay-layout-consensus (OLC) approach. In this paper, we propose an adaptation of the novel crow search algorithm (CSA) to solve the DNA fragment assembly problem following the OLC model. In order to accelerate the search process and improve the quality of the solutions, we combined CSA with a local search method. Using this combination we were able to obtain very accurate solutions for all the instances of the DNA fragment assembly problem we tested. In fact, our algorithm outperformed all other algorithms designed for the same purpose. Our contribution consists in the implementation of a new assembler for the DNA fragment assembly problem capable of finding for the first time the optimal solutions for 20 out of 30 instances. The approach we proposed to adapt CSA for a discrete optimization problem is a novelty. We preserved the semantics of the original algorithm by applying standard operators from evolutionary algorithms. Following the same approach can make adapting new algorithms for discrete problems more accessible and more efficient compared to mapping algorithms designed for continuous optimization to combinatorial problems. (C) 2018 Elsevier Ltd. All rights reserved.
机译：DNA的测序经过片段组装的步骤，这一步骤称为DNA片段组装问题（FAP）。片段组装被认为是NP难题，这意味着没有已知的多项式时间精确方法，因此需要元启发法。三种主要策略被广泛用于解决此问题：基于贪婪图的算法，de Bruijn图和覆盖-布局-共识（OLC）方法。在本文中，我们提出了一种新颖的乌鸦搜索算法（CSA）的改编，以解决遵循OLC模型的DNA片段组装问题。为了加快搜索过程并提高解决方案的质量，我们将CSA与本地搜索方法结合在一起。使用这种组合，我们能够针对我们测试的DNA片段装配问题的所有实例获得非常准确的解决方案。实际上，我们的算法优于为相同目的设计的所有其他算法。我们的贡献在于实现了针对DNA片段组装问题的新组装程序，该程序能够首次为30个实例中的20个找到最佳解决方案。我们提出的使CSA适应离散优化问题的方法是一种新颖的方法。通过应用进化算法中的标准运算符，我们保留了原始算法的语义。与为连续优化组合问题而设计的映射算法相比，采用相同的方法可以使针对离散问题的新算法更易于访问和更有效。 （C）2018 Elsevier Ltd.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号