编辑推荐：
在序列分析领域，最大公共子序列（MCS）研究意义重大。研究人员为解决现有工具不足问题，开展了构建 MCS 索引工具的研究。结果显示，McDag 工具可高效索引，对两条序列优势明显。其为相关领域序列分析提供了有力支持。
在计算机科学尤其是生物信息学领域，分析和比较符号序列是极为基础的问题。以往，研究人员常用最长公共子序列（LCS）来衡量序列间的相似性，但这种方法存在诸多局限性。比如，寻找任意数量字符串的单个 LCS 是 NP 完全问题，即使是两条字符串，其计算时间复杂度也为二次方。而且，一些关键但较短的序列可能无法扩展为与 LCS 等长的公共子序列，从而导致相关信息被忽视 。另一方面，若考虑所有公共子序列，又会包含大量冗余信息。在生物信息学研究中，基因测序数据的分析至关重要，例如在研究不同物种的基因相似性时，由于基因变异和测序噪声，精确匹配难以实现，此时最大公共子序列（MCS，即两个或多个字符串中包含的非连续符号的最大序列）的研究就显得尤为重要。然而，此前针对 MCS 的研究和工具相对匮乏，这促使研究人员开展相关研究，以填补这一空白。
来自意大利比萨大学（Università di Pisa）的研究人员 Giovanni Buzzega、Alessio Conte、Roberto Grossi 和 Giulia Punzi 开展了一项关于构建 MCS 索引工具的研究。他们构建了名为 McDag 的索引工具，该工具在概念上更为简单，构建速度也比现有方法更快。研究表明，McDag 能够在数分钟内对超过 10,000 个碱基对的序列对进行索引，且使用的节点数仅比最小所需节点数多 4 - 7% 。对于三条或更多序列的情况，虽然最小索引的节点数会显著增加，但 McDag 依然是首个能够对多个字符串的 MCS 进行索引的工具。这一研究成果发表在《Algorithms for Molecular Biology》上，为生物信息学、文本处理等领域的序列分析提供了更为高效的方法，推动了相关领域的发展。
研究人员在构建 McDag 时，运用了多种技术方法。首先，他们定义了 MCS 索引的相关概念，包括近似索引、确定性和共确定性等。通过 McConstruct 算法，从近似的共确定性最右索引中提取最大子序列，从而构建出确定性的 MCS 索引。此外，研究人员还对 CSA - all 进行优化，构建出 CSA - filtered 索引，将其作为 McConstruct 算法的输入，最终得到 McDag。在实验分析中，研究人员使用了 C++ 语言实现算法，并在特定的数据集（如随机序列和 HIV - 1 基因组数据）上进行测试。
1. 确定性 MCS 索引
研究人员引入 McConstruct 过程来构建 McDag 索引。先构建一个近似的共确定性最右索引 CSA - all，它是一种通用的公共子序列自动机的变体。通过从右向左读取每个字符串，并从其汇点开始反向构建，保证了该索引的共确定性和最右性。CSA - all 包含所有公共子序列，其正确性得到了证明，且复杂度分析表明其节点数和边数有一定的上限。随后，McConstruct 算法从 CSA - all 中提取最大子序列，构建出确定性的 MCS 索引。该算法的正确性也经过了严格证明，它通过过滤掉非最大序列，确保最终的索引只包含 MCS。在这个过程中，研究人员发现不能简单地用O(nk)个不同匹配来界定确定性 MCS 索引中的节点数。
2. McDag 索引
为了创建更优的索引，研究人员构建了 CSA - filtered。它通过两步构建，先构建确定性最左近似 MCS 索引 CSA - mixed，再用其过滤 CSA - all 中的非最大公共子序列。CSA - mixed 在构建时，从左向右读取字符串，通过筛选匹配来减少不必要的边和节点。CSA - filtered 在构建时，从右向左读取字符串，利用 CSA - mixed 作为指导，通过特定的关系和优先队列来确保正确构建。对于k=2的情况，还进行了优化，降低了时间复杂度。CSA - filtered 的正确性也得到了证明，它是一种共确定性最右近似 MCS 索引。最终，McDag 被定义为 McConstruct 算法以 CSA - filtered 为输入的输出，其正确性基于 CSA - filtered 和 McConstruct 的正确性。
3. 实验分析
研究人员对算法进行了实验评估。在实验设置上，使用 C++ 实现算法，在特定的机器上进行测试，并选择了随机序列和 HIV - 1 基因组数据作为数据集。在索引数据结构方面，实现了多种索引结构并进行评估。对于k=2的字符串，分析了索引大小和构建时间。结果显示，McDag 的节点数和边数比其他索引结构更少，更接近 MCS - minimized，且构建时间更短，优化后的构建路径在时间和空间上表现更优。对于k≥2的情况，研究发现随着k的增加，McDag 和 MCS - minimized 的节点数增长趋势与理论曲线不同，呈现出指数增长的趋势，这是由于消除非最大公共子序列导致额外节点和路径的产生。
研究人员成功构建了 McDag 这一索引工具，为多字符串 MCS 的索引提供了有效的解决方案。在两条字符串的情况下，McDag 展现出了高效性和紧凑性，为生物信息学、文本处理等领域的序列分析提供了有力支持。然而，对于三条或更多字符串的情况，虽然 McDag 能够实现索引功能，但索引大小会出现指数增长，这仍是一个待解决的问题。未来，研究人员计划通过先进的空间节省技术、并行 ism 和 SIMD 指令来扩展 McDag 在处理两条字符串时的可扩展性，致力于提供一个更强大、更通用的 MCS 索引工具，推动序列分析方法及其应用的进一步发展。
