Analyzing shared patterns across biological sequences represents an essential cornerstone of modern computational biology, yet conventional sequence comparison techniques frequently struggle to balance structural completeness with computational feasibility. In a study published in Algorithms for Molecular Biology, researchers Giovanni Buzzega, Alessio Conte, Roberto Grossi, and Giulia Punzi introduced McDag, a deterministic directed acyclic graph architecture and algorithmic framework engineered to index all maximal common subsequences across two or more input strings. The investigation establishes McDag as the first publicly available computational tool capable of indexing maximal common subsequences for real genomic data and generalizing the indexing formulation to arbitrary collections of k strings. Experimental evaluations on viral genomic sequences demonstrate that McDag can index pairs of biological sequences exceeding 10,000 base pairs within minutes, requiring only four to seven percent more nodes than the theoretical minimum deterministic index. However, when extended to three or more sequences, empirical evaluations reveal that the number of nodes in deterministic maximal common subsequence indices experiences exponential growth relative to sequence length, uncovering fundamental computational barriers in multi-sequence indexing.
Sequence comparison in computer science and bioinformatics has historically relied on finding exact matching substrings or identifying longest common subsequences. While searching for exact common substrings provides rapid matching, researchers emphasize that exact matches impose an excessively strict requirement when analyzing real-world biological data. Genomic sequences obtained from different biological specimens frequently undergo micro-variations, point mutations, and natural genetic divergence that alter target genes. Furthermore, biochemical sequencing instruments inevitably introduce experimental noise into genomic readouts, preventing identical sequence matching even when comparing distinct biological samples isolated from the exact same organism. To accommodate these biological variations, bioinformatics researchers frequently analyze common subsequences, which consist of ordered sequences of characters that appear across all examined strings without requiring contiguous positioning. In such subsequences, shared characters may be freely interleaved with non-matching symbols, allowing computational models to capture conserved functional motifs that would otherwise be discarded by contiguous substring alignment pipelines.
Because the total number of common subsequences between even two genetic sequences can grow exponentially, classical comparative algorithms typically restrict their search to the single longest common subsequence, widely designated as the LCS. Although LCS alignments serve as standard metrics for sequence alignment and biological similarity, the study highlights critical operational drawbacks inherent to this singular focus. First, identifying an LCS across an arbitrary collection of k strings is formally NP-complete, and determining the longest common subsequence for just two strings requires quadratic time under conditional fine-grained complexity lower bounds, such as the Strong Exponential Time Hypothesis and the Orthogonal Vectors Hypothesis. Second, an alignment based exclusively on the LCS can completely overlook biologically crucial motifs. For example, if two genetic sequences share a long, repetitive promoter sequence alongside a shorter, highly conserved functional region that cannot be mathematically extended to match the total length of the promoter sequence, an LCS-based analysis will discard the shorter critical sequence entirely. Conversely, attempting to capture all possible common subsequences using common subsequence automata floods the analysis with redundant, non-maximal subsequences that are strictly contained within longer common variants.
To overcome this analytical impasse, the research team focused on Maximal Common Subsequences, abbreviated as MCSs. A common subsequence is defined as an inclusion-maximal common subsequence if it cannot be extended by inserting any character at any position without ceasing to be a common subsequence across all input sequences. By definition, every longest common subsequence belongs to the set of maximal common subsequences, but the MCS formulation also preserves shorter, non-extendable shared segments that reflect distinct conserved biological elements. While recent algorithmic advancements introduced methods to enumerate maximal common subsequences, the authors note that the total number of MCS strings can remain exponential, making brute-force enumeration and physical storage impractical for practical genomics. Consequently, the development of a compact, deterministic index capable of representing, counting, and querying all maximal common subsequences without explicitly materializing an exponential string set emerged as a crucial theoretical and practical objective.
The mathematical foundation of McDag rests on a labeled directed acyclic graph denoted G = (V, E, l) containing a unique source node s marked with an opening delimiter and a single sink node t marked with a terminating delimiter. Every internal node in the graph corresponds to a specific character from the sequence alphabet and is associated with a k-dimensional match tuple tracking coordinates across the k input strings. The graph is structured such that every directed path running from the source to the sink spells out a unique maximal common subsequence, and conversely, every valid maximal common subsequence corresponds to exactly one path. The authors enforce strict determinism, requiring that all outgoing edges from any node lead to nodes with distinct character labels, which guarantees an out-degree bounded by the alphabet size and ensures that every prefix of an MCS traces a unique trajectory from the source. To prevent the graph from inadvertently generating non-maximal common subsequences, the construction characterizes and systematically eliminates structures designated as subsequence bubbles, defined as pairs of disjoint paths where one shorter path constitutes a proper subsequence of a longer alternative path between shared endpoints.
Constructing McDag efficiently requires a specialized two-stage processing pipeline that transforms an approximate index containing non-maximal common subsequences into a deterministic, maximal-only index. The core determinization engine, termed McConstruct, iterates through the nodes of an initial co-deterministic, rightmost approximate graph, filtering out dominated candidate matches that cannot lead to inclusion-maximal subsequences. In exploring construction efficiency, the authors proved that the runtime complexity of McConstruct is governed by the cumulative size of candidate node sets tracked during node expansion. To minimize this computational burden, the researchers developed an optimized intermediate data structure designated as CSA-filtered. Rather than deploying a standard common subsequence automaton that preserves all common subsequences, the framework first builds a deterministic leftmost approximate index, called CSA-mixed, by reading sequences left to right and discarding dominated transitions. Algorithm 4 then traverses the sequences in reverse to assemble CSA-filtered, using the leftmost automaton to prune unnecessary edges and non-maximal nodes before invoking McConstruct to yield the finalized McDag structure.
To evaluate the practical computational performance of McDag, the researchers implemented the algorithms in C++ compiled with native performance flags and executed comparative benchmarks on a dedicated server equipped with dual Intel Xeon Gold 5318Y processors and 989 gigabytes of random access memory under Ubuntu 22.04.2 LTS. The experimental benchmarks utilized two primary datasets: synthetic sequences generated across varying alphabet sizes and real genomic datasets comprising 43 complete HIV-1 genomes averaging 9,267 base pairs in length. In pairwise sequence comparisons with k = 2, McDag was evaluated alongside three benchmark graph architectures: M-Dag from prior literature, the baseline CSA-maximal graph derived from unoptimized subsequence automata, and the theoretical minimal deterministic index MCS-minimized obtained via Revuz minimization. Benchmark results showed that M-Dag and CSA-maximal suffered severe computational bottlenecks, triggering timeouts at 8,000 seconds when sequence lengths reached 2,300 and 5,700 base pairs, respectively. In contrast, McDag processed complete genome comparisons within 600 seconds, maintaining full scalability across sequences exceeding 10,000 base pairs.
Detailed structural measurements confirmed substantial efficiency improvements in index size and execution time for pairwise string analyses. While synthetic worst-case sequence constructions can theoretically force quadratic node counts, experimental evaluations across all real-world and synthetic datasets demonstrated that the total number of nodes and edges in McDag consistently remained below the square of the sequence length. In quantitative comparisons against the fully minimized theoretical automaton, McDag exhibited remarkable compactness, requiring only 4 to 7 percent more nodes than MCS-minimized, whereas M-Dag exceeded the minimum by 26 to 31 percent and CSA-maximal by 19 to 27 percent. In tests over 100 randomly selected pairs of HIV-1 sequences truncated to 3,000 base pairs, the filtering mechanism reduced the initial approximate graph from an average of 9.12 million edges in CSA-all to 2.37 million edges in CSA-filtered. Crucially, this edge pruning reduced the cumulative node set metric inside McConstruct from 18.21 million in CSA-maximal down to 7.21 million in McDag, directly accounting for the multi-order-of-magnitude reduction in execution runtime.
When extending the indexing framework to multiple sequences where k exceeds two, the experimental investigations revealed unexpected structural scaling behaviors. Because finding the longest path within an MCS index directly solves the NP-hard multiple longest common subsequence problem, computational experiments were restricted to shorter sequences across collections of three to six HIV-1 genomes. Although the researchers initially conjectured that the number of nodes in McDag would follow an O(n^k) polynomial upper bound matching the theoretical lower bounds of fine-grained complexity, logarithmic scale plots revealed a distinctly different pattern. While the intermediate CSA-filtered graph strictly adhered to the polynomial n^k trajectory, the finalized McDag and MCS-minimized graphs exhibited curves that became linear on logarithmic plots as sequence lengths increased, indicating an exponential growth rate relative to sequence length n. The researchers identified the structural origin of this exponential expansion in the rigorous determinization step: eliminating non-maximal common subsequences forces the creation of additional distinct matching nodes to prevent invalid path combinations, causing any deterministic MCS index to scale exponentially when k is greater than two.
The study provides a rigorous computational foundation for maximal common subsequence indexing while clarifying explicit boundaries for sequence analysis applications. For pairwise comparisons, McDag delivers an engineered, publicly accessible solution on GitHub capable of indexing genomic sequences within minutes, enabling rapid downstream queries including exact subsequence retrieval, length-bounded pattern matching, regular expression filtering, and structural counting without rebuilding the underlying graph. At the same time, the authors emphasize clear physical limitations: while McDag efficiently handles viral genomes and localized genetic segments of 10,000 base pairs, extensive eukaryotic chromosomes spanning millions of base pairs remain beyond immediate reach without further algorithmic developments such as advanced space-saving encodings, parallel processing, and SIMD hardware instructions. Furthermore, proving whether pairwise McDag size remains strictly bounded below n^2 for all arbitrary alphabets, as well as resolving whether any polynomial-sized deterministic MCS index can theoretically exist for k greater than two, remain open mathematical challenges for future research.
Subject of Research: Algorithmic indexing of maximal common subsequences across multiple genomic sequences using directed acyclic graphs
Article Title: \(\textsc {McDag}\): indexing maximal common subsequences for k strings
Article References: Buzzega, G., Conte, A., Grossi, R., & Punzi, G. (2025). $$\textsc {McDag}$$: indexing maximal common subsequences for k strings. Algorithms for Molecular Biology, 20(1), Article 6. https://doi.org/10.1186/s13015-025-00271-z
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00271-z
Keywords: maximal common subsequences, McDag, computational biology, sequence indexing, directed acyclic graphs, bioinformatics, longest common subsequence, string algorithms, automata theory, genomic sequence analysis, HIV-1 genome, fine-grained complexity, subsequence bubbles, McConstruct, co-determinism, graph determinization, algorithmic efficiency
News Source: Juliet Wilcox. (November 16, 2026). McDag Indexes Maximal Common Subsequences Across Multiple Genomic Sequences in Minutes. Scienmag.



