adjacent to at least one other short path. These branch vertices are denoted as repeat branches, as in the case of directed cycles. The repeat branches are detected in the spanning-treelike subgraph and their real edges are cut. With mate-pair information, it is possible to assign two repeat branches to each other. In this case, the path in between can be duplicated and re-linked in accordance with the mate-pair information. Here, our strategy is similar to the one described by Pevzner and Tang [20]. Path Extraction and Consensus Determination All the longest paths are calculated for the given spanning- treelike subgraph. For each leaf in the subgraph, the longest path is determined. For the end-vertices of these longest paths, the longest paths are again calculated. Then the resulting set of longest paths is scanned for paths that share a subpath with each other. For these paths, only the longest path is taken for the final set. Finally, the consensus is determined for each path in the final set of longest paths considering all overlap alignments and global alignments to contained reads. Algorithm to Integrate Left-Over Reads SUPERLOCAS is an extension of LOCAS that explicitly takes left-over reads into account when using LOCAS for local or homology-guided assemblies (Figure 2). First, an overlap graph for all left-over reads is built, called the left-over graph. Then, a LOCAS - A Low Coverage Assembler for Resequencing modified version of the basic assembly algorithm is applied to each block of the genome, which also deals with the integration of left-over reads. The extra step is applied after having built the overlap graph: first, the relevant left-over reads are selected by determining overlap alignments between local reads and left-over reads. For the selected left-over reads, the induced subgraph of the left-over graph is linked to the overlap graph of the local assembly. By extending the overlap graph with parts of the left- over graph, left-over reads are taken into account during the following assembly steps and can substantially elongate the resulting contigs. Results Assembly Algorithm and Extension for Homology-Guided Assemblies We have developed and implemented a new assembly algorithm in a software tool called LOCAS. The approach is based on the overlap-layout-consensus paradigm. Especially designed for data of low sequencing depth in the context of resequencing projects, LOCAS calculates alignment based overlaps instead of exact matches between reads. Furthermore, we have implemented an extension to LOCAS called SUPERLOCAS to support our homology-guided assembly approach. In this approach, the target genome is partitioned into blocks of given length. Next, SUPERLOCAS assembles each set of Figure 3. Performance comparison of low sequencing depth assembly. Illumina GAIIx reads were simulated at a sequencing depth of 7.56 for the first chromosome of A. thaliana Col-0. The reads were assigned to the reference sequence corresponding to their origin positions and partitioned into blocks of a length of 10 kb. The avgN50 (average N50) is plotted against the avgERR (average error rate) for the assembly tools LOCAS, EULER-SR, ABySS, VELVET and soapDeNovo. For each assembler, several runs are displayed corresponding to the different parameter settings. The data points of ABySS are drawn in orange, EULER-SR in green, LOCAS in red, VELVET in blue and soapDeNovo in turquoise. Each point represents one run. doi:10.1371/journal.pone.0023455.g003 PLoS ONE | www.plosone.org 4 August 2011 | Volume 6 | Issue 8 | e23455