基于最小边集的De Bruijn图定位算法

doi:10.12068/j.issn.1005-3026.2022.02.001

东北大学学报（自然科学版） ›› 2022, Vol. 43 ›› Issue (2): 153-159.DOI: 10.12068/j.issn.1005-3026.2022.02.001

• 信息与控制 • 下一篇

基于最小边集的De Bruijn图定位算法

于长永，金建宇，刘鹏，赵宇海

(东北大学计算机科学与工程学院，辽宁沈阳110169)

修回日期:2021-05-07 接受日期:2021-05-07 发布日期:2022-02-28
通讯作者: 于长永
作者简介:于长永(1981-)，男，辽宁海城人，东北大学副教授.
基金资助:
国家自然科学基金资助项目(61772124).

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

YU Chang-yong， JIN Jian-yu， LIU Peng， ZHAO Yu-hai

School of Computer Science & Engineering， Northeastern University， Shenyang 110169， China.

Revised:2021-05-07 Accepted:2021-05-07 Published:2022-02-28
Contact: YU Chang-yong
About author:-
Supported by:
-

摘要/Abstract

摘要： 针对基因序列比对问题提出了一种DBG(de Bruijn图)模型，称为MiniDBG.它可以存储最小边集的位置列表，并通过位置列表有效地定位图上的任何节点、边和路径，从而实现对基因的序列比对.介绍了MiniDBG模型及基于该模型的路径定位算法，并对算法进行了证明.同时将MiniDBG与基于BWT和基于位置列表的路径定位方法进行了比较，实验结果表明，在频繁比对的情况下，MiniDBG的性能优于其他两种方法.

关键词: 基因序列比对；De Bruijn图；最小边集；位置列表；路径定位算法

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

中图分类号:

TP274

于长永，金建宇，刘鹏，赵宇海. 基于最小边集的De Bruijn图定位算法[J]. 东北大学学报（自然科学版）, 2022, 43(2): 153-159.

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.

参考文献

[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.

基于最小边集的De Bruijn图定位算法

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	马树军，王英蕾，金铁铮，白昕晖. 一种融合单目信息的RGB-D SLAM优化方法[J]. 东北大学学报:自然科学版, 2020, 41(6): 841-846.
[2]	王璐，陈雪玮，郝丽玲，徐礼胜. 基于Lognormal函数的脉搏波分解可行性研究[J]. 东北大学学报:自然科学版, 2019, 40(12): 1695-1699.
[3]	张忠良，雒兴刚，汤建国，唐加福. 基于OVO分解策略的智能卷烟感官评估方法[J]. 东北大学学报:自然科学版, 2018, 39(1): 15-20.
[4]	康雁，宁国琛. 基于声源定位的头部姿态检测系统研究与实现[J]. 东北大学学报:自然科学版, 2018, 39(1): 26-31.
[5]	蒋芳芳，刘星航，宁国琛，耿若雪. 一种基于体震信号的快速ICA胎儿心搏信号提取方法[J]. 东北大学学报:自然科学版, 2017, 38(11): 1530-1533.
[6]	徐礼胜，薄红瑞，赵金野，窦元珠. 基于体动射频信号的睡眠分期[J]. 东北大学学报:自然科学版, 2016, 37(8): 1079-1083.
[7]	赵海，窦圣昶，李大舟，陈星池. 基于Lognormal函数的脉搏波数学建模[J]. 东北大学学报:自然科学版, 2016, 37(2): 169-173.
[8]	邓永刚，邸洪双，胡美源，张洁岑. 基于三点弯曲试验研究合金化镀层剥落机制[J]. 东北大学学报:自然科学版, 2016, 37(1): 49-53.
[9]	李凯，陈卫华. 零售商资金约束的多渠道供应链定价策略[J]. 东北大学学报:自然科学版, 2015, 36(10): 1511-1515.
[10]	史添玮，王宏，孙明星. 基于组合导航与EKPF飞行器的地形边界与面积估计[J]. 东北大学学报:自然科学版, 2015, 36(8): 1069-1073.
[11]	王国柱，刘建昌，李元. 稀疏性SVDD方法在故障检测中的应用研究[J]. 东北大学学报:自然科学版, 2015, 36(6): 761-765.
[12]	刘婷婷，张长胜，张斌，孙若男. 一种基于反馈策略的自适应选择人工蜂群算法[J]. 东北大学学报:自然科学版, 2015, 36(5): 618-622.
[13]	刘卓，柴天佑，汤健. 一种多尺度球磨机筒体振动频谱分析与建模方法[J]. 东北大学学报:自然科学版, 2015, 36(3): 305-308.
[14]	尹建东，孙洪赞，杨嘉文，郭启勇. 基于k-means簇分析提取DSC成像的脑动脉输入函数[J]. 东北大学学报:自然科学版, 2014, 35(12): 1677-1681.
[15]	张云洲，项姝，付文艳，贾子熙. 结合共线性因素的无线传感器网络DV-Hop定位算法[J]. 东北大学学报:自然科学版, 2014, 35(10): 1378-1381.