multiLCS

multiLCS implements a MATLAB parallel algorithm to identify the longest common subsequence (LCS) across multiple biological sequences for comparative genomic analysis.

Key Features:

• Parallel Algorithm Implementation: FAST_LCS implements a parallel algorithm that accelerates computation of the LCS among multiple sequences.
• Successor Table Construction: A successor table is constructed to identify all identical character pairs and their respective levels and to facilitate tracing back from pairs at the final level to determine the LCS.
• Effective Pruning Techniques: The algorithm incorporates pruning strategies that reduce computational complexity compared with other leading LCS algorithms.
• Optimized for MPP systems: The implementation targets Massively Parallel Processing (MPP) systems to utilize parallel execution models for large datasets.

Scientific Applications:

• Comparative genomics: Identifying common subsequences across multiple gene sequences to support genomic comparison and analysis.
• Large-scale sequence analysis: Handling and analyzing large biological sequence datasets, including data from databases such as the TIGR database.
• Algorithm benchmarking: Experimental results demonstrate superior performance relative to other leading LCS algorithms, supporting method comparison and selection.

Methodology:

Constructs a successor table to enumerate identical character pairs and levels and traces back from final-level pairs to obtain the LCS; implements the FAST_LCS parallel algorithm with pruning strategies and parallel execution on MPP systems; memory for two sequences X and Y of lengths n and m is max{4(n+1) + 4(m+1), L} where L is the number of identical character pairs; sequential time complexity is O(L) and parallel time complexity is O(|LCS(X,Y)|), with analogous O(L) sequential and O(|LCS(X1,...,Xn)|) parallel complexities for n sequences.