Overlap graph method 


Overlap graph method search for term

In this graph, each vertex represent a read and two vertices are joined by an edge if the 2 fragments overlap. Next, the graph is simplified by the removal of transitive edges and contained edges. Finally, chains of nodes are collapsed into « chunks » treated as single nodes in the graph. The Myers method finds a maxium likelihood non-cyclic (Hamiltonian) path through the graph and infer layout of the reads from this path (Edwards 2009). The overlap consensus assembly method uses the overlap between sequence reads to create a link between them. The contig is eventually formed by reading along the links as far as possible. Of course, multiple reads, errors, repeats and other ambiguities mean that there are multiple forks in the path through the links, and it is the differences in the ways of navigating through these ambiguities that differentiates the different methods. With short reads, overlap consensus assembly suffers from two main problems. First, the short read length means the overlaps must be calculated over a large proportion of the read to retain accuracy, and second, the huge number of reads increases the number of links, so that the contig path is difficult to compute. Some short-read assemblers that are based on this method include SSAKE, VCAKE, SHARCGS and Roche's proprietary 454 assembler, Newbler. (McLean 2009)