A path recorder algorithm for Multiple Longest Common Subsequences (MLCS) problems.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Mining

Background:

• The Multiple Longest Common Subsequence (MLCS) problem is fundamental in data mining but computationally intensive.
• Existing algorithms struggle with long and large-scale sequence datasets due to high time and space complexity.

Purpose of the Study:

• To develop an efficient method for solving large-scale MLCS problems.
• To introduce a novel Path Recorder Directed Acyclic Graph (PRDAG) model and Path Recorder Algorithm (PRA).

Main Methods:

• Transformed the MLCS problem into finding the longest path in a Directed Acyclic Graph (DAG).
• Optimized DAG construction by eliminating redundant nodes and retaining only the longest paths.
• Developed the Path Recorder Algorithm (PRA) to efficiently traverse the optimized DAG.

Main Results:

• The PRDAG model significantly reduces DAG size, saving memory and search time.
• Empirical experiments on DNA and protein sequences show superior performance over leading algorithms.
• The method is particularly effective for large-scale MLCS challenges.

Conclusions:

• The proposed PRDAG model and PRA offer an efficient solution for large-scale MLCS problems.
• This approach overcomes the limitations of existing algorithms in terms of computational resources.
• The findings have significant implications for sequence analysis in bioinformatics and data mining.