In this paper we show how to use one or more assembled or partially assembled genome as the basis for a compressed full-text index of its readset. Specifically, we build a labelled tree by taking the assembled genome as a trunk and grafting onto it the reads that align to it, at the starting positions of their alignments. Next, we compute the eXtended Burrows-Wheeler Transform (XBWT) of the resulting labelled tree and build a compressed full-text index on that. Although this index can occasionally return false positives, it is usually much more compact than the alternatives. Following the established practice for datasets with many repetitions, we compare different full-text indices by looking at the number of runs in the transformed strings. For a human Chr19 readset our preliminary experiments show that eliminating separators characters from the EBWT reduces the number of runs by 19\%, from 220 million to 178 million, and using the XBWT reduces it by a further 15\%, to 150 million.
翻译:在本文中,我们展示了如何使用一个或一个以上组装或部分组装的基因组作为其重新组合的压缩全文索引的基础。 具体地说, 我们用组装的基因组作为树干, 将与其对齐的读数放在对齐的起始位置上, 并把它粘贴在树上。 其次, 我们计算由此而成的标签树的 Extendive Burrows- Wheeler 变形 (XBWT), 并据此建立压缩全文索引。 虽然该指数有时可以返回假正数, 但通常比替代物要紧得多。 按照已确立的重复的数据集惯例, 我们比较不同的全文索引, 查看在变形线中运行的数量。 对于人类 Chr19 进行的初步实验显示, 从 EBWT 中去除分隔符数减少19 ⁇, 从2.2亿 减少到1.78亿, 并使用 XBWT再减少15亿, 到1.5亿 。