A De Bruijn Graph Localization Algorithm Based on Minimal Set of Edges

doi:10.12068/j.issn.1005-3026.2022.02.001

Abstract

Abstract: A DBG(de Bruijn graph)model called MiniDBG for gene sequence alignment is proposed. It can store the position list of the minimum edge set， and effectively locate any node， edge and path on the graph through the position list， so as to achieve sequence alignment of genes. The MiniDBG model and the path location algorithm based on the model are introduced， and the algorithm is proved. Meanwhile， the MiniDBG is compared with the path location method based on BWT and location list. Experimental results show that the performance of MiniDBG is better than those of the other two methods in the case of frequent alignment.

Key words: gene sequence alignment; de Bruijn graph; minimal set of edges; position list; path location algorithm

CLC Number:

TP274

YU Chang-yong， JIN Jian-yu， LIU Peng， ZHAO Yu-hai. A De Bruijn Graph Localization Algorithm Based on Minimal Set of Edges[J]. Journal of Northeastern University(Natural Science), 2022, 43(2): 153-159.

References

[1]Miller J R，Koren S，Sutton G.Assembly algorithms for next-generation sequencing data［J］.Genomics，2010，95(6):315-327.
[2]Schatz M C，Delcher A L，Salzberg S L.Assembly of large genomes using second-generation sequencing［J］.Genome Research，2010，20(9):1165-1173.
[3]Minkin I，Pham H，Starostina E，et al.C-Sibelia:an easy-to-use and highly accurate tool for bacterial genome comparison［J/OL］.F1000 Research，2013［2021-04-10］.https://f1000research.com/articles/2-258/v1.DOI:10.12688/f1000research.2-258.v1.
[4]Minkin I，Patel A，Kolmogorov M，et al.A scalable and comprehensive synteny block generation tool for closely related microbial genomes［M］// Algorithms in Bioinformatics.Berlin:Springer Berlin Heidelberg，2013:215-229.
[5]Pham S K，Pevzner P A.DRIMM-Synteny:decomposing genomes into evolutionary conserved segments［J］.Bioinformatics，2010，26(20):2509-2516.
[6]Raphael B，Zhi D G，Tang H X，et al.A novel method for multiple alignment of sequences with repeated and shuffled elements［J］.Genome Research，2004，14(11):2336-2346.
[7]Dilthey A，Cox C，Iqbal Z，et al.Improved genome inference in the MHC using a population reference graph［J］.Nature Genetics，2015，47:682-688.
[8]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:226-232.
[9]Bradley P，Gordon N C，Walker T M，et al.Rapid antibiotic-resistance predictions from genome sequence data for Staphylococcus aureus and Mycobacterium tuberculosis［J］.Nature Communications，2015，6:10063.
[10]Xin H，Nahar S，Zhu R，et al.Optimal seed solver:optimizing seed selection in read mapping［J］.Bioinformatics，2016，32(11):1632-1642.
[11]Liu B，Guo H Z，Brudno M，et al.deBGA:read alignment with de Bruijn graph-based seed and extension［J］.Bioinformatics，2016，32(21):3224-3232.
[12]Minkin I，Pham S，Medvedev P.TwoPaCo:an efficient algorithm to build the compacted de Bruijn graph from many complete genomes［J］.Bioinformatics，2017，33(24):4024-4032.
[13]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 & Bioinformatics，2019［2021-04-09］.https:/ieeexplore.ieee.org/document/8703070.DOI:10.1109/TCBB.2019.2913932.
[14]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):i169-i177.
[15]Alipanahi B，Kuhnle A，Puglisi S J，et al.Succinct dynamic de Bruijn graphs［J］.Bioinformatics，2021，37(14):1946-1952
[16]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.
[17]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):D756-D763.