A Novel Efficient Graph Model for the Multiple Longest Common Subsequences (MLCS) Problem.

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Design

Background:

• The Multiple Longest Common Subsequences (MLCS) problem is a computationally challenging NP-hard problem with significant applications.
• Existing exact approaches, often relying on dominant point graphs (a type of directed acyclic graph - DAG), suffer from high time and space complexity, limiting their scalability for large datasets.

Purpose of the Study:

• To develop a more time and space efficient graph model for solving the MLCS problem.
• To overcome the limitations of existing dominant point graph-based methods for large-scale and long sequence analysis.

Main Methods:

• Introduction of a novel graph model named Leveled-DAG.
• The Leveled-DAG efficiently prunes non-contributory nodes during construction, minimizing memory usage by retaining only current and essential previous nodes.
• The model directly stores all MLCS in a single final node, eliminating post-processing search steps.

Main Results:

• The Leveled-DAG approach demonstrates superior time and space efficiency compared to state-of-the-art algorithms.
• Performance improvements are particularly notable when applied to large-scale and long biological sequences.
• Experimental validation on real biological sequence data confirms the efficacy of the proposed method.

Conclusions:

• The Leveled-DAG offers a significant advancement in efficiently solving the MLCS problem.
• This novel approach enhances the applicability of MLCS algorithms to large biological sequence datasets.
• The Leveled-DAG provides a scalable and memory-efficient solution for complex sequence analysis tasks.