: indexing maximal common subsequences for k strings

Area of Science:

• Bioinformatics
• Computational Biology
• Computer Science

Background:

• Sequence analysis is fundamental in computer science and bioinformatics.
• Maximal Common Subsequences (MCSs) are inclusion-maximal common subsequences, a generalization of common substrings/subsequences.
• MCSs have received limited attention despite their fundamental nature.

Purpose of the Study:

• To engineer recent advancements in MCSs into a practical, publicly available tool.
• To demonstrate the tool's capability to index MCSs in real genomic data.
• To generalize MCS indexing to multiple strings.

Main Methods:

• Development of a practical tool, $$, for indexing Maximal Common Subsequences.
• Engineering and simplification of recent MCS algorithms.
• Experimental evaluation on real genomic data pairs and triplets.

Main Results:

• The tool successfully indexes pairs of sequences exceeding 10,000 base pairs within minutes.
• The indexing process utilizes only 4-7% more than the minimum required nodes for pairs.
• Indexing for three or more sequences shows a significant increase in the number of nodes.

Conclusions:

• The developed tool is the first to publicly index MCSs of genomic data.
• The tool provides an efficient solution for analyzing large genomic sequences.
• Generalizing MCS indexing to multiple strings presents computational challenges regarding index size.