LOCAS - A Low Coverage Assembler for Resequencing Figure 1. Transformation of the overlap alignment graph into the path graph. In (A), an overlap graph is shown, and, for some read sequences, the underlying alignment information is displayed. In (B), the corresponding path graph is displayed. For each unique path in the overlap graph an inner edge is introduced in the path graph, represented by a solid line. For example, the unique path between b and d in the overlap graph is represented by the inner edge (b90, d9) in the path graph. If two vertices in the path graph represent the two ends of the same read, then a real edge is presented between them in the path graph. These real edges are shown as dashed lines. An example is the real edge (d9, d0). The vertices d9 and d0 represent the same read since they both correspond to vertex d in the overlap graph but they represent the two different ends of the read, since the read of d overlaps with the read of b and e but at different ends, which is displayed in (A). doi:10.1371/journal.pone.0023455.g001 errors or false alignments (Figure S5). An algorithm is applied to the path graph that calculates a spanning-treelike subgraph. The algorithm works as follows. First, all real edges are placed according to their score in a priority queue. This edge score measures the average quality of the read alignments and the average read coverage from reads underlying the edge vertices. The edges of the subgraph are selected iteratively in the path graph. In each step, the edge with the highest score is considered for selection. If a directed cycle will not be introduced in the subgraph if a certain edge were selected, the edge is selected. If the candidate edge would introduce a directed cycle in the subgraph, the edge is not selected, the cycle is cleaned of all short dangling paths and then cut open at all remaining branch vertices. Next, the remains of the opened directed cycle are recorded with its branches, called repeat branches. See Figure S6 for an illustration of the cutting operation. If an undirected cycle with a similar sequence is introduced with the selection of the candidate edge, then the edge is selected and the whole cycle is marked in the subgraph. For the introduction of an undirected cycle with a dissimilar sequence, the edge is not selected. It is likely that some alignments are not detected due to sequencing errors. In this case, the affected repeats are not represented by directed cycles in the spanning-treelike subgraph. In order to detect and solve these repeat structures, the algorithm scans for fragmentary directed cycles. They correspond to paths in the graph that link two branch vertices so that each of them is Figure 2. Workflow of SUPERLOCAS. The figure shows the workflow of the algorithm of SUPERLOCAS. The initial steps are illustrated: the left- over reads with the constructed left-over overlap graph, and the reads that are aligned against the reference sequence and partitioned into blocks. Next, the steps that are executed consecutively for each block are shown: the construction of the overlap graph, the insertion of edges between both graphs and the procedure until contigs are reported for the merged graph. doi:10.1371/journal.pone.0023455.g002 PLoS ONE | www.plosone.org 3 August 2011 | Volume 6 | Issue 8 | e23455