Efficient DNA Fragment Assembly Based on Discrete Slime Mould Algorithm
摘要
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.