UNLABELLED: In response to increasing amounts of sequencing data, faster and faster aligners need to become available. Here, we introduce BRAT-nova, a completely rewritten and improved implementation of the mapping tool BRAT-BW for bisulfite-treated reads (BS-Seq). BRAT-nova is very fast and accurate. On the human genome, BRAT-nova is 2-7 times faster than state-of-the-art aligners, while maintaining the same percentage of uniquely mapped reads and space usage. On synthetic reads, BRAT-nova is 2-8 times faster than state-of-the-art aligners while maintaining similar mapping accuracy, methylation call accuracy, methylation level accuracy and space efficiency. AVAILABILITY AND IMPLEMENTATION: The software is available in the public domain at http://compbio.cs.ucr.edu/brat/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: We introduce BRAT-BW, a fast, accurate and memory-efficient tool that maps bisulfite-treated short reads (BS-seq) to a reference genome using the FM-index (Burrows-Wheeler transform). BRAT-BW is significantly more memory efficient and faster on longer reads than current state-of-the-art tools for BS-seq data, without compromising on accuracy. BRAT-BW is a part of a software suite for genome-wide single base-resolution methylation data analysis that supports single and paired-end reads and includes a tool for estimation of methylation level at each cytosine. AVAILABILITY: The software is available in the public domain at http://compbio.cs.ucr.edu/brat/.

The newest generation of sequencing instruments, such as Illumina/Solexa Genome Analyzer and ABI SOLiD, can generate hundreds of millions of short DNA “reads” from a single run. These reads must be matched against a reference genome to identify their original location. Due to sequencing errors or variations in the sequenced genome, the matching procedure must allow a variable but limited number of mismatches. This problem is a version of the classic approximate string matching where a long text is searched for the occurrence of a set of short patterns. Typical strategies to speed up the matching involve elaborate hashing schemes that exploit the inherent repetitions of the data. However, such large data structures are not well suited for FPGA implementations. In this paper we evaluate an FPGA implementation that uses a “naive” approach which checks every possible read-genome alignment. We compare the performance of the naive approach to popular software tools currently used to map short reads to a reference genome showing a speedup of up to 4X over the fastest software tool.

Abstract Summary: We present a new, accurate and efficient tool for mapping short reads obtained from the Illumina Genome Analyzer following sodium bisulfite conversion. Our tool, BRAT, supports single and paired-end reads and handles input files containing reads and mates of different lengths. BRAT is faster, maps more unique paired-end reads and has higher accuracy than existing programs. The software package includes tools to end-trim low-quality bases of the reads and to report nucleotide counts for mapped reads on the reference genome. Availability: The source code is freely available for download at http://compbio.cs.ucr.edu/brat/ and is distributed as Open Source software under the GPLv3.0. Contact: [email protected]

Bioinformatics (2010) 26(4), 572–573 The authors would like to apologize for the erroneous statements on the accuracy of the mapping for mrsFAST (Hormozdiari et al., 2009). The parameters for the insert size used for msrFAST to obtain Figure 1 and Table 1 were not correct; using the correct parameters would have yield higher accuracy than the one reported. At the time of the initial simulation there was no documentation available regarding the distance between the reads for paired-end, so we deduced the definition for the distance from the output files of mrsFAST. For 32 bases paired-end reads (Table 1), we used insert size range from 106 to 306 (called min and max, respectively, in mrsFAST), but the correct values should have been [43, 243]. For 24 bases paired-end reads (Fig. 1), we used [136, 324] whereas the correct values should have been [89, 277]. For 64 bases paired-end reads (Fig. 1), we used [136, 364], but the correct parameters should have been [9, 237].