MLCS

MLCS computes all longest common subsequences across multiple DNA sequences to support multiple-sequence alignment and comparative analysis.

Key Features:

• Character Merging Scheme: Merges consecutive identical characters within sequences, leveraging consecutively repeated characters in DNA to shorten sequence length and reduce storage requirements.
• Weighted Directed Acyclic Graph (DAG): Constructs a weighted DAG on merged sequences that is significantly smaller than traditional MLCS graphs, reducing space and time costs during computation.
• Efficiency: Experimental results demonstrate that the algorithm outperforms existing state-of-the-art MLCS methods in computational speed and memory usage for large-scale problems.

Scientific Applications:

• DNA sequence alignment: Identifies regions of similarity among DNA sequences to inform functional, structural, or evolutionary analyses.
• Data mining and text editing: Applies to tasks requiring efficient identification of multiple longest common subsequences across character sequences in data mining and text-editing contexts.

Methodology:

The method first applies a character merging scheme to reduce sequence length and storage, and then constructs a weighted DAG on the merged sequences to compute the MLCS, minimizing time and space costs.