Wild-AC：支持通配符的改进Aho-Corasick算法在蛋白质组学肽段-蛋白映射中的高效多模式字符串匹配

《BMC Bioinformatics》：Wild-AC: A fast, index-free multi-pattern string matching algorithm with wildcard support for proteomics

【字体：大中小】 时间：2026年10月11日 来源：BMC Bioinformatics 4.4

编辑推荐：

　　摘要背景支持通配符的高效多模式字符串匹配在蛋白质组学中至关重要，需要将肽映射到包含模糊氨基酸（例如 B、Z、X）的蛋白质数据库中。现有方法要么需要预处理（例如 FM 索引），要么无法处理文本中的通配符。结果我们提出了 Wild-AC，这是一种修改后的 Aho-Corasick

摘要

背景

支持通配符的高效多模式字符串匹配在蛋白质组学中至关重要，需要将肽映射到包含模糊氨基酸（例如 B、Z、X）的蛋白质数据库中。现有方法要么需要预处理（例如 FM 索引），要么无法处理文本中的通配符。

结果

我们提出了 Wild-AC，这是一种修改后的 Aho-Corasick 算法，通过将搜索分支为并行的‘侦察’路径（每种可能的通配符表示一条路径）来支持文本中的通配符，同时在常见无通配符情况下，未修改的主搜索不受影响地继续进行。Wild-AC 在速度上优于 FM 索引（通配符情况），并与 Wu-Manber（精确搜索）相当或超过，适用于现实的蛋白质组学工作负载，即 1000–500,000 个肽模式（平均长度约 18 个氨基酸）在 3 × 10⁶–2.1 × 10⁸ 个字符的蛋白质数据库（文本）中进行搜索。在通配符率掩蔽为 5% 的数据库上，Wild-AC 对大型肽集保持了其优势，而 FM 索引则更适合小型数据集。它不需要索引，能很好地随模式数量扩展，并支持多线程。C++ 实现版本开源地址为 https://github.com/Wild-AC/Wild-AC。

结论

Wild-AC 扩展了 Aho-Corasick 算法以支持通配符，在考虑模糊氨基酸的肽 - 蛋白映射任务中优于 FM-Index 和 Wu-Manber。

图形摘要

两个搜索过程，分别标记为侦察 1 和侦察 2，探索一个节点编号为 0 到 10 的树结构。侦察 1 沿着从节点 0 经过节点 1、2 和 3 的路径，依次匹配字符 A、D 和 Q。侦察 2 沿着从节点 0 经过节点 8、9 和 10 的不同路径，依次匹配字符 E、N 和 Q。节点 7、3、5 和 10 被高亮显示，表示模式匹配。该树包括标记有字符的直接转换的实线箭头和表示节点之间附加链接的虚线箭头。列在树旁边的主要特征包括多模式匹配、通配符支持、无需索引、针对大型模式集的快速性能、多线程以及开源可用性。

背景

支持通配符的高效多模式字符串匹配在蛋白质组学中至关重要，需要将肽映射到包含模糊氨基酸（例如 B、Z、X）的蛋白质数据库中。现有方法要么需要预处理（例如 FM 索引），要么无法处理文本中的通配符。

结果

我们提出了 Wild-AC，这是一种修改后的 Aho-Corasick 算法，通过将搜索分支为并行的‘侦察’路径（每种可能的通配符表示一条路径）来支持文本中的通配符，同时在常见无通配符情况下，未修改的主搜索不受影响地继续进行。Wild-AC 在速度上优于 FM 索引（通配符情况），并与 Wu-Manber（精确搜索）相当或超过，适用于现实的蛋白质组学工作负载，即 1000–500,000 个肽模式（平均长度约 18 个氨基酸）在 3 × 10⁶–2.1 × 10⁸ 个字符的蛋白质数据库（文本）中进行搜索。在通配符率掩蔽为 5% 的数据库上，Wild-AC 对大型肽集保持了其优势，而 FM 索引则更适合小型数据集。它不需要索引，能很好地随模式数量扩展，并支持多线程。C++ 实现版本开源地址为 https://github.com/Wild-AC/Wild-AC。