SUMMARY: The sequencing of bisulfite-treated DNA (Bi-Seq) is becoming a gold standard for methylation studies. The mapping of Bi-Seq reads is complex and requires special alignment algorithms. This problem is particularly relevant for SOLiD color space, where the bisulfite conversion C/T changes two adjacent colors into 16 possible combinations. Here, we present an algorithm that efficiently aligns Bi-Seq reads obtained either from SOLiD or Illumina. An accompanying methylation-caller program creates a genomic view of methylated and unmethylated Cs on both DNA strands. AVAILABILITY AND IMPLEMENTATION: The algorithm has been implemented as an option of the program PASS, freely available at http://pass.cribi.unipd.it. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: Standard DNA alignment programs are inadequate to manage the data produced by new generation DNA sequencers. To answer this problem, we developed PASS with the objective of improving execution time and sensitivity when compared with other available programs. PASS performs fast gapped and ungapped alignments of short DNA sequences onto a reference DNA, typically a genomic sequence. It is designed to handle a huge amount of reads such as those generated by Solexa, SOLiD or 454 technologies. The algorithm is based on a data structure that holds in RAM the index of the genomic positions of 'seed' words (typically 11 and 12 bases) as well as an index of the precomputed scores of short words (typically seven and eight bases) aligned against each other. After building the genomic index, the program scans every query sequence performing three steps: (1) it finds matching seed words in the genome; (2) for every match checks the precomputed alignment of the short flanking regions; (3) if passes step 2, then it performs an exact dynamic alignment of a narrow region around the match. The performance of the program is very striking both for sensitivity and speed. For instance, gap alignment is achieved hundreds of times faster than BLAST and several times faster than SOAP, especially when gaps are allowed. Furthermore, PASS has a higher sensitivity when compared with the other available programs. AVAILABILITY AND IMPLEMENTATION: Source code and binaries are freely available for download at http://pass.cribi.unipd.it, implemented in C++and supported on Linux and Windows.

MOTIVATION: DNA repeats are a common feature of most genomic sequences. Their de novo identification is still difficult despite being a crucial step in genomic analysis and oligonucleotides design. Several efficient algorithms based on word counting are available, but too short words decrease specificity while long words decrease sensitivity, particularly in degenerated repeats. RESULTS: The Repeat Analysis Program (RAP) is based on a new word-counting algorithm optimized for high resolution repeat identification using gapped words. Many different overlapping gapped words can be counted at the same genomic position, thus producing a better signal than the single ungapped word. This results in better specificity both in terms of low-frequency detection, being able to identify sequences repeated only once, and highly divergent detection, producing a generally high score in most intron sequences. AVAILABILITY: The program is freely available for non-profit organizations, upon request to the authors. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: The program has been tested on the Caenorhabditis elegans genome using word lengths of 12, 14 and 16 bases. The full analysis has been implemented in the UCSC Genome Browser and is accessible at http://genome.cribi.unipd.it.