Fast and exact quantification of motif occurrences in biological sequences.
Fast and exact quantification of motif occurrences in biological sequences.
复制标题
DOI：
10.1186/s12859-021-04355-6
复制
发表时间：
2021-09-18
影响因子：
3
通讯作者：
Boucher C
中科院分区：
文献类型：
--
作者：
Prosperi M;Marini S;Boucher C
基序的识别和量化对于遗传疾病、基因进化、转录位点和其他生物学机制的研究非常重要。马尔可夫假设下模体计数分布的精确估计公式计算复杂度高，不适用于大型模体集。近似公式，例如基于复合泊松，更快，但可靠的p值计算仍然具有挑战性。在这里，我们介绍'motif_prob'，一个快速实现的图案计数分布的精确公式，通过渐进逼近任意精度。我们的实现加快了精确的计算，通常是不切实际的，使其成为可行的，并取代目前采用的计算。我们在Perl和C++语言中实现了motif_prob，使用高效的错误限制迭代过程获得确切的公式，在精度，运行时基准方面与最先进的工具（例如MoSDi）进行比较，沿着细菌基序表征的真实用例。我们的软件能够在普通笔记本电脑上在一分钟内处理超过500万个碱基的基因组长度的100万个基序（13-31个碱基），Perl和C++代码的运行时间比MoSDi小几个数量级（快50-1000倍），即使使用快速复合泊松近似（快60-120倍）。在现实世界的用例中，我们首先展示了motif_prob与MoSDi的一致性，然后使用抗菌素耐药基因中发现的基序，当细菌具有不同的GC含量时，p值量化对于富集量化至关重要。该软件和代码源可在https://github.com/DataIntellSystLab/motif_prob上获得MIT许可证。motif_prob软件是一个多平台和高效的开源解决方案，用于计算模体的精确频率分布。它可以与基序发现/表征工具集成，用于量化富集和与具有精确p值的预期频率范围的偏差，而不会损失数据处理效率。
Identification of motifs and quantification of their occurrences are important for the study of genetic diseases, gene evolution, transcription sites, and other biological mechanisms. Exact formulae for estimating count distributions of motifs under Markovian assumptions have high computational complexity and are impractical to be used on large motif sets. Approximated formulae, e.g. based on compound Poisson, are faster, but reliable p value calculation remains challenging. Here, we introduce ‘motif_prob’, a fast implementation of an exact formula for motif count distribution through progressive approximation with arbitrary precision. Our implementation speeds up the exact calculation, usually impractical, making it feasible and posit to substitute currently employed heuristics. We implement motif_prob in both Perl and C+ + languages, using an efficient error-bound iterative process for the exact formula, providing comparison with state-of-the-art tools (e.g. MoSDi) in terms of precision, run time benchmarks, along with a real-world use case on bacterial motif characterization. Our software is able to process a million of motifs (13–31 bases) over genome lengths of 5 million bases within the minute on a regular laptop, and the run times for both the Perl and C+ + code are several orders of magnitude smaller (50–1000× faster) than MoSDi, even when using their fast compound Poisson approximation (60–120× faster). In the real-world use cases, we first show the consistency of motif_prob with MoSDi, and then how the p-value quantification is crucial for enrichment quantification when bacteria have different GC content, using motifs found in antimicrobial resistance genes. The software and the code sources are available under the MIT license at https://github.com/DataIntellSystLab/motif_prob. The motif_prob software is a multi-platform and efficient open source solution for calculating exact frequency distributions of motifs. It can be integrated with motif discovery/characterization tools for quantifying enrichment and deviation from expected frequency ranges with exact p values, without loss in data processing efficiency.