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

Area of Science:

• Bioinformatics
• Computational Biology
• Data Mining

Background:

• The multiple longest common subsequence (MLCS) problem is crucial in various fields, including bioinformatics and data mining.
• Existing algorithms struggle with large-scale MLCS problems due to increasing sequence length and number.
• Current methods like dynamic programming and dominant point-based algorithms are often ineffective and inefficient.

Purpose of the Study:

• To develop a fast and memory-efficient algorithm for solving the MLCS problem.
• To address the limitations of existing algorithms for large-scale sequence analysis.
• To improve the efficiency of finding longest common subsequences in multiple character sequences.

Main Methods:

• A character merging scheme is proposed to shorten DNA sequences by merging consecutively repeated characters.
• A weighted directed acyclic graph (DAG) is constructed, significantly smaller than traditional DAGs used for MLCS.
• The algorithm leverages these techniques to reduce space and time complexity.

Main Results:

• The proposed algorithm demonstrates superior performance compared to state-of-the-art methods.
• Experimental results show significant improvements in both time and space costs.
• The character merging and weighted DAG approaches effectively reduce computational overhead.

Conclusions:

• The developed algorithm offers a significant advancement in solving the MLCS problem, particularly for large datasets.
• This method provides a more efficient and memory-saving solution for sequence analysis tasks.
• The approach is highly applicable to bioinformatics and DNA alignment challenges.