and

We present an algorithm to generate a set of highly reliable overlaps based on identifying repeat k-mers. This method does not require uniform coverage. We also describe an error correction method based on multi-sequence comparison, that allows extending usable sequence in reads trimmed to 16 % error rate. We use a version of the Phrap assembly program that uses only overlaps computed by the UMD overlapper, called PhrapUMD. We integrate the University of Maryland algorithms with Baylor’s ATLAS assembler applied to Rattus norvegicus. Starting with the same data as the Nov. 2002 ATLAS assembly, we compare our results to 4.5 Mbp of rat sequence in 21 BACs that have been finished. We find that after extension and error correction, (i) the reads are up to 30 % longer than reads trimmed to 2%; (ii) the average error rate across the extended reads is about 3 in 10,000 bases, with 88 % of the extended reads matching finished sequence exactly across their entire length; and (iii) PhrapUMD with these reads and our reliable overlaps produces a draft assembly of the rat which has no misassemblies and increases the coverage of finished sequence from 93.7 % to 96.7%, while simultaneously reducing the base error rate from 4.5 to 2.0 errors per 10,000 bases. ∗For questions or comments, please write t