一种针对大规模Read Mapping的高效DBG索引方法

doi:10.12068/j.issn.1005-3026.2023.06.002

摘要/Abstract

摘要： 为了能够回答生物信息学中关于de Bruijn graph(DBG)的两个问题——①对于任意的k-mer，回答其是否为DBG的顶点，②对于DBG的任意顶点，回答其邻接信息(入边和出边)，提出了一种针对大规模read mapping的高效DBG索引方法.本文将以上两个问题转化为非重复多路径上的k-mer和(k+1)-mer的确切查找问题，并利用FM-index进行解决.首先，对给定的参考序列进行压缩，即非重复多路径的发现，从而压缩了序列中大量存在的重复(k+1)-mer.其次，基于非重复多路径FM-index对DBG进行索引.查找k-mer是否出现在DBG上，若找到，给出该k-mer的直接前驱和直接后继结点，从而提高时空效率.最后，在62种大肠杆菌菌株的基因组上进行实验.实验结果表明，所提出的方法可以高效地对多参考序列的DBG进行索引.

关键词: de Bruijn graph；索引；read mapping(序列映射)；FM-index；参考序列

Abstract: In order to answer two questions about de Bruijn graph(DBG) in bioinformatics: ① For any k-mer， answer whether it is the vertex of DBG; ② For any vertex of DBG， answer its adjacency information(incoming edge and outgoing edge)， an efficient DBG indexing method for large-scale read mapping is proposed. In this paper， the above two questions are transformed into the exact finding problem of k-mer and (k+1)-mer on non-repetitive multipath， and are solved by using FM-index. Firstly， a given reference sequence is compressed， which is the discovery of non-repetitive multipaths， thereby compressing the presence of large-scale repetitive (k+1)-mers in the sequence. Secondly， the DBG is indexed based on the non-repetitive multipath FM-index. The k-mer is searched whether it appears on the DBG， and if so， the direct predecessor and direct successor nodes of the k-mer are provided to improve the spatial-temporal efficiency. Finally， experiments are performed on the genomes of 62 E. coli strains. The experimental results show that the method proposed can efficiently index the DBG of multi-reference sequences.

Key words: de Bruijn graph; index; read mapping; FM-index; reference sequence

中图分类号:

TP274

于长永，李俊杰，马海涛，赵宇海. 一种针对大规模Read Mapping的高效DBG索引方法[J]. 东北大学学报（自然科学版）, 2023, 44(6): 770-776.

YU Chang-yong， LI Jun-jie， MA Hai-tao， ZHAO Yu-hai. An Efficient DBG Indexing Method for Large-Scale Read Mapping[J]. Journal of Northeastern University(Natural Science), 2023, 44(6): 770-776.

参考文献

[1]El-Metwally S，Ouda O M，Helmy M.Next-generation sequencing platforms［J］.Springer New York，2014，7(4):37-44.
[2]Zhang H W，Chan Y D，Fan K C，et al.Fast and efficient short read mapping based on a succinct Hash index［J］.BMC Bioinformatics，2018，19(1):92-105.
[3]Burrows M，Wheeler D J.A block-sorting lossless data compression algorithm［J］.Technical Report Digital SRC Research Report，1994，124(1):1-24.
[4]Kim J，Chen L，Xie X.Improving read mapping using additional prefix grams［J］.BMC Bioinformatics，2014，15(1):42-52.
[5]Li R Q，Li Y R，Kristiansen K，et al.SOAP: short oligonucleotide alignment program［J］.Bioinformatics，2008，24(5):713-714.
[6]Rumble S M，Lacroute P，Dalca A V，et al.SHRiMP: accurate mapping of short color-space reads［J］.Public Library of Science Computational Biology，2009，5(5):e1000386.
[7]Homer N，Merriman B，Nelson S F.BFAST: an alignment tool for large scale genome resequencing［J］.Public Library of Science ONE，2009，4(11):e7767.
[8]Li H，Richard D.Fast and accurate short read alignment with Burrows-Wheeler transform［J］.Bioinformatics，2010，25(14):1754-1760.
[9]Langmead B，Salzberg S L.Fast gapped-read alignment with Bowtie 2［J］.Nature Methods，2012，9(4):357-359.
[10]Li R Q，Yu C，Li Y R，et al.SOAP2: an improved ultrafast tool for short read alignment［J］.Bioinformatics，2009，25(15):1966-1972.
[11]Ferragina P，Manzini G.Opportunistic data structures with applications［C］//Foundations of Computer Science.Redondo Beach: IEEE，2000:390-398.
[12]Simon G.A de Bruijn graph approach to the quantification of closely-related genomes in a microbial community［J］.Journal of Computational Biology，2012，19(6):814-825.
[13]Ye Y Z，Tang H X.Utilizing de Bruijn graph of metagenome assembly for metatranscriptome analysis［J］.Bioinformatics，2016，32(7):1001-1008.
[14]Liu B，Guo H Z，Michael B，et al.deBGA: read alignment with de Bruijn graph-based seed and extension［J］.Bioinformatics，2016，32(21):3224-3232.
[15]Fatemeh A，Hirak S，Avi S，et al.A space and time-efficient index for the compacted colored de Bruijn graph［J］.Bioinformatics，2018，34(13):169-177.
[16]Bowe A，Onodera T，Sadakane K，et al.Succinct de Bruijn graphs［C］//Workshop on Algorithms in Bioinformatics.Berlin:Springer，2012: 225-235.
[17]Muggli M D，Alexander B，Noyes N R，et al.Succinct colored de Bruijn graphs［J］.Bioinformatics，2017，33(20):3181-3187.
[18]Almodaresi F，Pandey P，Patro R.Rainbowfish: a succinct colored de Bruijn graph representation［C］//Workshop on Algorithms in Bioinformatics.Dagstuhl，2017: 1-15.
[19]Grabherr M G，Haas B J，Yassour M，et al.Full-length transcriptome assembly from RNA-Seq data without a reference genome［J］.Nature Biotechnology，2011，29(7):644-652.
[20]Haas B J，Papanicolaou A，Yassour M，et al.Transcript sequence reconstruction from RNA-seq using the Trinity platform for reference generation and analysis［J］.Nature Protocols，2013，8(8):1494-1512.
[21]Isaac T，Garimella K V，Zamin I，et al.Integrating long-range connectivity information into de Bruijn graphs［J］.Bioinformatics，2018，34(15):2556-2565.
[22]Limasset A，Cazaux B，Rivals E，et al.Read mapping on de Bruijn graphs［J］.BMC Bioinformatics，2016，17(1):237-248.
[23]Iqbal Z，Caccamo M，Turner I，et al.De novo assembly and genotyping of variants using colored de Bruijn graphs［J］.Nature Genetics，2012，44(2):226-257.
[24]Alipanahi B，Kuhnle A，Puglisi S J，et al.Succinct dynamic de Bruijn graphs［J］.Bioinformatics，2021，37(14):1946-1952.
[25]Guo H Z，Fu Y L，Gao Y，et al.deGSM: memory scalable construction of large scale de Bruijn graph［J］.IEEE/ACM Transactions on Computational Biology and Bioinformatics，2021，18(6):2157-2166.
[26]Xin H Y，Shao M F，Carl K.Context-aware seeds for read mapping［J］.Algorithms for Molecular Biology，2020，15(1):10-21.
[27]Pruitt K D，Brown G R，Hiatt S M，et al.RefSeq: an update on mammalian reference sequences［J］.Nucleic Acids Research，2014，42(D1):756-763.