In contrast to de novo assembly, homology-guided (or comparative) assembly approaches are more appropriate to discover novel sequence regions in eukaryotic genomes. Like the alignment- consensus approach, homology-guided assembly approaches exploit available reference genome assemblies from the same or closely related species. One strategy to perform homology-guided assembly starts with aligning short reads to a reference followed by local assemblies of reads that are aligned within the same regions (called blocks). We will refer to local assemblies based on alignment information within a block as reassembly. Reassembly can also benefit from incorporating reads that cannot be aligned (i.e. left-over reads) as they often originate from insertions or highly polymorphic regions, and therefore can potentially elongate the reassembled sequence on either side. Currently available assembly tools do not provide time-efficient methods to incorporate left-over reads for consecutive execution of multiple reassemblies. The set of left-over reads can be huge compared to the set of reads belonging to one block of the sequenced genome. Left-over reads consist not only of reads from highly polymorphic regions but also of erroneous reads, which, in our experience, can comprise about 5% to 20% of all reads from a sample. Since existing assemblers do not distinguish between aligned reads and left-over reads, they would have to assemble all left-over reads for each block over and over, leading to an unacceptable increase in runtime. Genome resequencing is often performed at low read coverage or sequencing depth. This results from a simple cost-benefit analysis: even with a sequencing depth of 76, most of the reference genome is covered by aligned reads, enabling the detection of most SNPs and small indels. However existing short read assemblers based on the de Bruijn graph paradigm such as VELVET [14], EULER-SR [15] and ABySS [16] are not well suited for low sequencing depth assembly as they typically require coverages of 206 to 306 [14]. Furthermore, de Bruijn graph assemblers rely on exact matches of sub-regions (kmers) of reads and do not calculate overlap alignments. Consequently, they cannot detect overlaps of reads with a substantial number of mismatches. For low sequencing depth assembly, however, it is necessary to include as many overlaps as possible in order to assemble low-coverage regions. We have developed a new assembly tool, LOCAS (LOw Coverage Assembly Software), with two main goals in mind: 1) allowing for de novo assembly at low sequence coverage, 2) support whole genome homology-guided assembly approaches by incor- porating left-over reads. Thus LOCAS is designed for assembling short to medium sized reads either de novo or in a homology-guided fashion using an overlap-layout-consensus approach. It explicitly handles data of low sequencing depth by allowing mismatches in the overlap calculation of reads. Further, to improve homology- guided assembly, it optionally takes advantage of the given alignment positions of reads relative to a reference sequence. An extension of LOCAS, called SUPERLOCAS, efficiently handles left-over reads. It calculates an overlap graph for the left-over reads once and recruits relevant overlapping parts of this graph during each reassembly quickly and efficiently. We show that LOCAS and SUPERLOCAS produce assemblies that are often better than those obtained by existing short read assemblers at sequencing depth of 7.56 as measured by N50 size and error rate. Methods LOCAS - A Low Coverage Assembler for Resequencing between all reads, an overlap graph is built. The graph is reduced and transformed into a path graph in which the vertices represent the unique paths of the overlap graph. Contigs are finally generated by extraction of appropriate paths from the path graph. To adjust this approach to short-read datasets of low sequencing depth, we modified the algorithm that selects the final paths in the path graph to handle a higher amount of single reads and a shorter read length. The higher amount of reads increases the complexity of the graph. Moreover, the shorter read lengths lead to shorter overlap alignments, also contributing to the complexity of the graph. In addition, more false overlap alignments are found for a shorter alignment length. We modified the algorithm to handle the increased number of false alignments and the larger graph as well as the relative increase of branches in the graph. Paths are selected in the path graph using a greedy strategy that aims at maximizing the total coverage of used reads and the total quality of the alignments used. Overlap Detection and Overlap Alignment Graph Pairs of potentially overlapping reads are detected with the help of an enhanced suffix array as implemented by the SeqAn library [19]. The suffix array is built for all reads followed by identification of all pairs of reads sharing an identical kmer. Overlap alignments are calculated for each pair with a minimal overlap length and a maximal number of mismatches given as input parameters to the assembly tool. The alignment information is represented by an overlap graph. Each vertex of the graph represents a read and each edge represents an alignment between the reads of the connected vertices. Two types of edge exist. An overlap edge corresponds to an overlap alignment. A containment edge represents a global alignment. Containment edges indicate that one read is aligned over its full length to the other read. If the reads are not equally long, then one read will be contained. A weight is assigned to each edge that corresponds to the length of the alignment. Further, a score is given that is equal to the alignment score describing the quality of the alignment. In the next step, an exemplar vertex is chosen for each set of vertices that are all connected to each other by containment edges. The exemplar is the longest read with the highest alignment score to the other reads in the set. For all other vertices represented by the exemplar, all overlap edges are removed. See Figure S3 for an illustration of the reduction. Reduction and Path Graph The overlap graph is reduced by removing all transitive edges. Each edge et = (v1, v2) with a weight wt is transitive if two edges e1 = (v1, w) and e2 = (w, v2) exist with weights w1 and w2, respectively, where wt#w1 and wt#w2. See Figure S4 for an illustration. Unique paths in the overlap graph are detected and merged. This is done during a transformation of the overlap graph into a path graph. Each unique path of maximal length in the overlap graph is represented by two vertices and an inner edge in the path graph. The two vertices in the path graph represent the ends of the path or, more precisely, the outer ends of the first and the last read sequence on the path. Further, we insert real edges that represent the adjacencies between unique paths in the overlap graph. A real edge is set for two vertices in the path graph if these vertices represent different ends of the same read. This is illustrated in Figure 1. LOCAS is based on the classical overlap-layout-consensus approach. We extended the approach described by Kececioglu and Myers [17,18], which was originally developed for assembling Sanger reads. After calculating an approximation of all alignments Solving Sequencing Errors and Repeat Structures Sequencing errors and repeat structures correspond to cycles in the path graph. They are called directed cycles if they represent repeat structures and undirected cycles if the represent sequencing PLoS ONE | www.plosone.org 2 August 2011 | Volume 6 | Issue 8 | e23455