A fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment

Abstract

Motivation: Multiple longest common subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing in sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point-based algorithms become ineffective and inefficient, especially for large-scale MLCS problems.

Results: In this paper, by considering the characteristics of DNA sequences with many consecutively repeated characters, we first design a character merging scheme which merges the consecutively repeated characters in the sequences. As a result, it shortens the length of sequences considered and saves the space of storing all sequences. To further reduce the space and time costs, we construct a weighted directed acyclic graph which is much smaller than widely used directed acyclic graph for MLCS problems. Based on these techniques, we propose a fast and memory efficient algorithm for MLCS problems. Finally, the experiments are conducted and the proposed algorithm is compared with several state-of-the art algorithms. The experimental results show that the proposed algorithm performs better than the compared state-of-the art algorithms in both time and space costs.

Availability and implementation: https://www.ncbi.nlm.nih.gov/nuccore and https://github.com/liusen1006/MLCS.