Refining the r-index
Refining the r-index
复制标题
DOI：
10.1016/j.tcs.2019.08.005
复制
发表时间：
2020-04-06
影响因子：
1.1
通讯作者：
Tomohiro, I
中科院分区：
文献类型：
--
作者：
Bannai, Hideo;Gagie, Travis;Tomohiro, I
Gagie，Navarro和Prezza的r-index（SODA，2018）承诺通过允许我们索引整个基因组数据库来加速DNA比对和变异调用，前提是可以克服某些障碍。在本文中，我们首先加强和简化了Policriti和Prezza的支点引理（DCC '16; Mimica，2017），它启发了r-索引并在其实现中发挥了重要作用。然后，我们展示了如何在向数据库添加新基因组后有效地更新r索引，这在实践中可能是至关重要的。作为这一结果的副产品，我们获得了在线版本的Policriti和Prezza的算法，用于从游程长度压缩的Burrows-Wheeler变换构建LZ 77解析。我们的实验证明了这三个结果的实用性。最后，我们展示了如何增强r-索引，使得给定新的基因组和对数据库的快速随机访问，我们可以快速计算新基因组相对于数据库的匹配统计和最大精确匹配。(C)2019 Elsevier B. V.版权所有。
Gagie, Navarro and Prezza's r-index (SODA, 2018) promises to speed up DNA alignment and variation calling by allowing us to index entire genomic databases, provided certain obstacles can be overcome. In this paper we first strengthen and simplify Policriti and Prezza's Toehold Lemma (DCC '16; Algorithmica, 2017), which inspired the r-index and plays an important role in its implementation. We then show how to update the r-index efficiently after adding a new genome to the database, which is likely to be vital in practice. As a by-product of this result, we obtain an online version of Policriti and Prezza's algorithm for constructing the LZ77 parse from a run-length compressed Burrows-Wheeler Transform. Our experiments demonstrate the practicality of all three of these results. Finally, we show how to augment the r-index such that, given a new genome and fast random access to the database, we can quickly compute the matching statistics and maximal exact matches of the new genome with respect to the database. (C) 2019 Elsevier B.V. All rights reserved.