Improved Node and Arc Multiplicity Estimation in De Bruijn Graphs Using Approximate Inference in Conditional Random Fields

In de novo genome assembly using short Illumina reads, the accurate determination of node and arc multiplicities in a de Bruijn graph has a large impact on the quality and contiguity of the assembly. The multiplicity estimates of nodes and arcs guide the cleaning of the de Bruijn graph by identifying spurious nodes and arcs that correspond to sequencing errors. Additionally, they can be used to guide repeat resolution. Here, we model the entire de Bruijn graph and the accompanying read coverage information with a single Conditional Random Field (CRF) model. We show that approximate inference using Loopy Belief Propagation (LBP) on our model improves multiplicity assignment accuracy within feasible runtimes. The order in which messages are passed has a large influence on the speed of LBP convergence. Little theoretical guarantees exist and the conditions for convergence are not easily checked as our CRF model contains higher-order interactions. Therefore, we also present an empirical evaluation of several message passing schemes that may guide future users of LBP on CRFs with higher-order interactions in their choice of message passing scheme.

Automated summary

In de novo genome assembly, accurate determination of node and arc multiplicities in a de Bruijn graph is crucial for improving assembly quality and contiguity. A Conditional Random Field (CRF) model is proposed to model the de Bruijn graph and read coverage information. Loopy Belief Propagation (LBP) is applied for approximate inference to improve multiplicity assignment accuracy. The order of message passing in LBP greatly affects its convergence speed, and an empirical evaluation of different message passing schemes is presented.