Compressing and indexing aligned readsets

T Gagie, G Gourdel, G Manzini - arXiv preprint arXiv:1809.07320, 2018 - arxiv.org
arXiv preprint arXiv:1809.07320, 2018arxiv.org
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 …
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.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果