A New Multiple DNA and Protein Sequences Alignment Method based on Evolutionary Algorithms

Abstract

Introduction: The study of life and the detection of gene functions is an important issue in biological science. Multiple sequences alignment methods measure the similarity of DNA sequences. Nonetheless, when the size of genome sequences is increased, we encounter with the lack of memory and increasing the run time. Therefore, a fast method with a suitable accuracy for genome alignment has a significant impact on the analysis of long sequences.

Methods: We introduce a new method in which, it first divides each sequence into short sequences. Then, it uses evolutionary algorithms to align the sequences.

Results: The proposed method has been evaluated in seven datasets with different number of nucleotides per DNA sequence (18,000 to 14 million) and compared to five popular multiple sequences alignment methods. The highest accuracy for the variola bacterium dataset is 93% and the highest alignment rate is 0.6 per minute for this bacterium.

Conclusion: Most multiple alignment methods in short sequences or datasets with only a few sequences have good accuracy while require high computational time for longer sequences. The proposed algorithm overcomes this drawback by aligning long sequences in an acceptable time and maintaining accuracy as well as optimal memory usage.