Message passing algorithm for inferring consensus sequence from next-generation sequencing data

In order to determine an individual´s DNA sequence, sequencing platforms often employ shotgun sequencing where multiple identical copies of the DNA strand of interest are randomly fragmented and then the nucleotide content of the short fragments is determined. Assembly of the long DNA strand from short fragments is a computationally challenging task that has attracted significant amount of attention in recent years. We formulate reference-guided assembly as the inference problem on a bipartite graph and solve it using a message-passing algorithm. The message-passing algorithm does not need to rely on the quality score information which expresses reliability of the short reads. To assess the performance of the proposed methodology, we derive an expression for the probability of error of a genie-aided MAP consensus scheme. Simulation results on a Neisseria meningitidis data set demonstrate that the proposed message-passing algorithm performs close to the idealistic MAP consensus scheme.