PHONI: Streamed Matching Statistics with Multi-Genome References.
PHONI: Streamed Matching Statistics with Multi-Genome References.
复制标题
DOI：
10.1109/dcc50243.2021.00027
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Rossi M
中科院分区：
文献类型：
--
作者：
Boucher C;Gagie T;Tomohiro I;Köppl D;Langmead B;Manzini G;Navarro G;Pacheco A;Rossi M
计算模式与文本的匹配统计量是生物信息学中的一项基本任务，但当文本是高度压缩的基因组数据库时，这是一项艰巨的任务。Bannai等人为这种情况给出了一个有效的解决方案，Rossi等人最近实现了该方案，但它使用了两次模式传递，并在第一次传递过程中为每个字符缓冲一个指针。在本文中，我们简化了他们的解决方案，并使其流，代价是稍微放慢速度。这意味着，首先，我们可以并行计算几个长模式（如整个人类染色体）的匹配统计数据，同时仍然使用合理数量的RAM;其次，我们可以在线计算匹配统计数据，延迟较低，从而快速识别模式何时变得相对于数据库不可压缩。我们的代码可在https://github.com/koeppl/phoni上获得。
Computing the matching statistics of patterns with respect to a text is a fundamental task in bioinformatics, but a formidable one when the text is a highly compressed genomic database. Bannai et al. gave an efficient solution for this case, which Rossi et al. recently implemented, but it uses two passes over the patterns and buffers a pointer for each character during the first pass. In this paper, we simplify their solution and make it streaming, at the cost of slowing it down slightly. This means that, first, we can compute the matching statistics of several long patterns (such as whole human chromosomes) in parallel while still using a reasonable amount of RAM; second, we can compute matching statistics online with low latency and thus quickly recognize when a pattern becomes incompressible relative to the database. Our code is available at https://github.com/koeppl/phoni.
登录
查看更多内容
影响因子：
2.5
作者：
Charikar, M;Lehman, E;Shelat, A
通讯作者：
Shelat, A
影响因子：
1.1
作者：
Bannai, Hideo;Gagie, Travis;Tomohiro, I
通讯作者：
Tomohiro, I
DOI：
10.1016/j.jda.2010.08.004
发表时间：
2010-12-01
期刊：
JOURNAL OF DISCRETE ALGORITHMS
影响因子：
--
作者：
Ilie, Lucian;Navarro, Gonzalo;Tinta, Liviu
通讯作者：
Tinta, Liviu
影响因子：
1.7
作者：
Kuhnle, Alan;Mun, Taher;Manzini, Giovanni
通讯作者：
Manzini, Giovanni
影响因子：
1.1
作者：
Rytter, W
通讯作者：
Rytter, W