AGNES: Adaptive Graph Neural Network and Dynamic Programming Hybrid Framework for Real-Time Nanopore Seed Chaining
Jahidul Arafat, Sanjaya Poudel
纳米孔测序可实现读取超过10千基数的实时长读DNA测序,但12-15%的固有错误率对读对齐提出了重大的计算挑战。 关键的种子链步骤必须连接读取和参考基因组之间的精确k-mer匹配,同时过滤虚假的匹配,但最先进的方法依赖于无法适应不同基因组上下文的固定间隙惩罚功能,包括串联重复和结构变体。 本文介绍了RawHash3,这是一个混合框架,将图形神经网络与经典动态编程相结合,用于自适应种子链,同时保持实时性能,同时提供统计保证。 我们将种子链正式化为图形学习,其中种子构成具有12维特征向量的节点,边缘编码8维的空间关系,包括间隙一致性。 我们的架构采用三层EdgeConv GNN,具有基于置信的方法选择,可以在学习指导和算法回退之间动态切换。 对1000个合成纳米孔读取5,200个测试种子进行综合评估表明,RawHash3实现了99.94%的精度和40.07%的召回,比基线的相对改善显着25.0 % , p小于0.001。 该系统保持1.59ms的中位推理延迟,满足实时限制,同时表现出卓越的稳健性,100%的成功率低于20%的标签腐败,而基线退化为30.3%。 交叉验证证实了建立图神经网络的稳定性,作为生产基因组学管道的可行方法。
Nanopore sequencing enables real-time long-read DNA sequencing with reads exceeding 10 kilobases, but inherent error rates of 12-15 percent present significant computational challenges for read alignment. The critical seed chaining step must connect exact k-mer matches between reads and reference genomes while filtering spurious matches, yet state-of-the-art methods rely on fixed gap penalty functions unable to adapt to varying genomic contexts including tandem repeats and structural variants. T...