McDag indexes maximal common subsequences of sequence pairs over 10,000 base pairs in minutes
Authors of Algorithms for Molecular Biology built the first publicly available tool to index maximal common subsequences of real genomic data and extended the definition to k strings.

Researchers Giovanni Buzzega, Alessio Conte, Roberto Grossi and Giulia Punzi described McDag, a tool for indexing maximal common subsequences (MCSs) of genomic sequences, in the journal Algorithms for Molecular Biology. According to the authors, it is the first publicly available tool that can index MCSs of real genomic data. It indexes pairs of sequences exceeding 10,000 base pairs within minutes, using only 4–7% more nodes than the minimum required biomedcentral.com
Algorithms for Molecular Biologybiomedcentral.comOpen source ↗.
Why maximal common subsequences
An MCS is an inclusion-maximal sequence of non-contiguous symbols common to two or more strings: no character can be inserted into it without it ceasing to be common to all inputs. Every longest common subsequence (LCS) is an MCS, but MCSs also keep shorter, non-extendable shared segments that an LCS-based analysis discards.
The authors note that finding an LCS for an arbitrary number k of strings is NP-complete, and for two strings it requires quadratic time under conditional lower bounds. Common subsequence automata, in turn, include many non-maximal subsequences. The number of MCSs can also be exponential, so listing and storing them is impractical, which motivates a compact index.
How the index is built
McDag is a deterministic labeled directed acyclic graph with one source and one sink. Each source-to-sink path spells exactly one MCS, and each MCS corresponds to exactly one path. Outgoing edges of any node lead to nodes with distinct labels. The construction removes "subsequence bubbles", pairs of paths where the shorter one is a subsequence of the longer biomedcentral.com
Algorithms for Molecular Biologybiomedcentral.comOpen source ↗.
Construction runs in two stages. First, an approximate index, CSA-mixed, is built by reading the sequences left to right and discarding dominated transitions. Then the sequences are traversed in reverse to assemble CSA-filtered, which is passed to the McConstruct procedure that produces the final McDag. The authors implemented the algorithms in C++ and ran benchmarks on a server with two Intel Xeon Gold 5318Y processors.
The definition of McDag is generalized to multiple strings. For three or more sequences, the authors observe experimentally that the minimum index may show a significant increase in the number of nodes. According to the publication of the work, the experiments used viral genomic sequences.



