DNA fragment assembly is an important step in the downstream data processing of DNA sequencing and is crucial for sequencing accuracy. Nevertheless, current DNA fragment assembly algorithms still deficient in assembly speed and accuracy. In this paper we propose a DNA fragment assembly method based on discrete slime mould algorithm (DSMA) by analyzing the overlap-layout-consensus methods. DSMA incorporates the PALS-Fit operator and the OX operator based on the slime mold algorithm to map the solution space into DNA short-read fragment numbers and incorporates a local search method. The experimental results show that this algorithm is able to find optimal solutions for 27 out of 30 test instances, which is a 20% improvement compared to other state-of-the-art algorithms, illustrating the improvement of search speed and the quality of the solution. Moreover, DSMA fetched competitive results in the DNA fragment assembly benchmark dataset. In conclusion, the proposed DSMA can solve the DNA fragment assembly more efficiently and achieve efficient reconstruction of large-scale DNA short-read fragments.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient DNA Fragment Assembly Based on Discrete Slime Mould Algorithm

  • Shuqing Si,
  • Ben Cao,
  • Qi Shao,
  • Lijun Sun,
  • Yanfen Zheng,
  • Bin Wang,
  • Pan Zheng

摘要

DNA fragment assembly is an important step in the downstream data processing of DNA sequencing and is crucial for sequencing accuracy. Nevertheless, current DNA fragment assembly algorithms still deficient in assembly speed and accuracy. In this paper we propose a DNA fragment assembly method based on discrete slime mould algorithm (DSMA) by analyzing the overlap-layout-consensus methods. DSMA incorporates the PALS-Fit operator and the OX operator based on the slime mold algorithm to map the solution space into DNA short-read fragment numbers and incorporates a local search method. The experimental results show that this algorithm is able to find optimal solutions for 27 out of 30 test instances, which is a 20% improvement compared to other state-of-the-art algorithms, illustrating the improvement of search speed and the quality of the solution. Moreover, DSMA fetched competitive results in the DNA fragment assembly benchmark dataset. In conclusion, the proposed DSMA can solve the DNA fragment assembly more efficiently and achieve efficient reconstruction of large-scale DNA short-read fragments.