Improving Phrap-Based Assembly of the Rat Using “Reliable” Overlaps

Michael Roberts, Aleksey V. Zimin, Wayne Hayes et al. · 2008

Read Improving Phrap-Based Assembly of the Rat Using “Reliable” Overlaps by Michael Roberts, Aleksey V. Zimin, Wayne Hayes et al. (2008) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/plos-pone-0001836.txt.

Introduction

Michael Roberts, Aleksey V. Zimin, Wayne Hayes, and their co-authors improved genome assembly software in a 2008 PLOS ONE research article. The assembly methods used for whole-genome shotgun data have a major impact on the quality of resulting draft genomes. Shotgun sequencing reads a genome in millions of fragments that software must overlap and join.

Their algorithm generates a set of 'reliable' overlaps by identifying repeat k-mers. Those are short repeated sequences that cause false joins, and the method improves Phrap-based assembly of the rat genome. The full text gives the algorithm and the before-and-after assembly quality. Every genome project of the era depended on such assembly hygiene; one repeat mishandled can scramble whole chromosomes.

Catalog record

CREATORMichael Roberts, Aleksey V. Zimin, Wayne Hayes et al.
YEAR2008
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
LICENSECreative Commons Attribution License
RIGHTSCC BY
SOURCEPLOS ONE

Source: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0001836

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improving Phrap-Based Assembly of the Rat Using “Reliable” Overlaps Authors: Michael Roberts, Aleksey V. Zimin, Wayne Hayes, Brian R. Hunt, Cevat Ustun, James R. White, Paul Havlak, James Yorke Published: 2008, PLOS ONE DOI: 10.1371/journal.pone.0001836 ABSTRACT The assembly methods used for whole-genome shotgun (WGS) data have a major impact on the quality of resulting draft genomes. We present a novel algorithm to generate a set of “reliable” overlaps based on identifying repeat k-mers. To demonstrate the benefits of using reliable overlaps, we have created a version of the Phrap assembly program that uses only overlaps from a specific list. We call this version PhrapUMD . Integrating PhrapUMD and our “reliable-overlap” algorithm with the Baylor College of Medicine assembler, Atlas, we assemble the BACs from the Rattus norvegicus genome project. Starting with the same data as the Nov. 2002 Atlas assembly, we compare our results and the Atlas assembly to the 4.3 Mb of rat sequence in the 21 BACs that have been finished. Our version of the draft assembly of the 21 BACs increases the coverage of finished sequence from 93.4% to 96.3%, while simultaneously reducing the base error rate from 4.5 to 1.1 errors per 10,000 bases. There are a number of ways of assessing the relative merits of assemblies when the finished sequence is available. If one views the overall quality of an assembly as proportional to the inverse of the product of the error rate and sequence missed, then the assembly presented here is seven times better. The UMD Overlapper with options for reliable overlaps is available from the authors at http://www.genome.umd.edu . We also provide the changes to the Phrap source code enabling it to use only the reliable overlaps. INTRODUCTION Most genomes for which draft assemblies are available have been assembled using the whole-genome shotgun (WGS) method or a hybrid-WGS technique. In the WGS method many copies of the genome are randomly fractured into fragments, with estimated lengths that usually run from several thousand bases (Kb) (plasmids and fosmids) to some that are well over 100 Kb (Bacterial Articial Chromosomes or BACs). The actual length of each fragment is likely to differ from the estimated length by perhaps 10% to 20%. The sequences of the two ends of each fragment are then read imperfectly. The sequence of each end is called a read . Two reads that were created from opposite ends of the same fragment are said to be mates , and they form a mate-pair . Each read has up to 1000 bases. As the sequence is created, each base is assigned a quality score related to the probability that the base is being reported incorrectly [1] , [2] . Enough fragments are created so that a typical base in the genome is represented in several reads, usually about seven to thirteen. Given this data and no more, the WGS assembly problem is to assemble the genome as completely and correctly as possible. Several genome assembly programs have been developed, such as the TIGR assembler [3] , the Celera Assembler [4] , Atlas [5] , Arachne [6] , Phusion [7] , JAZZ [8] , and PCAP [9] . Although appearing deceptively simple, genome assembly is remarkably difficult in practice. This is evident by the fact that despite using the same input, different assemblers can produce draft assemblies that differ considerably in size and error rates. Several assembly programs (e.g. Phusion and Atlas) utilize Phrap [10] at the early stages of the assembly. Phrap is also widely used as a standalone tool for creating local assemblies of the BAC-sized (up to about 250K bases) regions of genomic sequence. Given a set of reads and optional quality scores, Phrap computes overlaps and assembles the reads into contigs, generating a read multi-alignment, a contig sequence and sequence quality information. We have produced PhrapUMD , a modified version of Phrap that allows the user to control which overlaps Phrap uses in building contigs. We paired PhrapUMD with the UMD Overlapper [11] , which corrects errors in the reads and accurately computes a set of high-quality overlaps that we call “reliable”. This paper shows how a Phrap-based assembler can be improved by simply substituting the UMD Overlapper and PhrapUMD for Phrap in its pipeline. To demonstrate the power of our techniques, we integrated them into Atlas, the Baylor College of Medicine (Baylor) assembly program. We used the modified Atlas to produce assemblies of approximately 20,000 BACs from the rat genome project. We report here on how the modification improves Atlas' ability to assemble the genome of the rat Rattus Norvegicus [12] . We note that the methods that we propose and evaluate in this manuscript are mostly useful for assembly programs utilizing Phrap for building contigs. We do not expect that the use of “reliable” overlaps will bring about any improvements for assembly programs that do not use Phrap, such as Celera Assembler, Arachne, or PCAP. Still, there are many centers that use Phrap for assembling genomes or fragments of genomes, such as National Intramural Sequencing Center at NIH, Human Genome Sequencing Center at Baylor College of Medicine, Sanger Centre, and many others. The methods discussed in this paper will be of great benefit to these centers. We evaluate our assembly methods by comparing the resulting draft with the finished sequence of a part of the genome. By commonly accepted definition, the finished sequence is a gapless sequence with less than 1 error per 10000 bases, whose validity has been checked and corrected with additional local sequencing. However, it is important to note that this sequence may not be completely correct [13] . METHODS One of the first steps in creating an assembly from WGS data is to determine which reads overlap each other based on comparison of their sequences. The fact that two reads' sequences agree over some interval does not necessarily imply that these reads came from the same part of the genome. They might have come from different copies of a repetitive region. We call the set of all overlaps between reads plausible . Some portion of the plausible overlaps is spurious due to repetitive regions in the genomes. In this paper, we describe a technique that identifies a subset of the plausible overlaps that we call reliable . The reason for creating reliable overlaps is to avoid creating misassemblies at the early stages of the assembly when the contiguous chunks of sequence (contigs) are built using only overlap information. Figure 1a shows a scenario where a genome contains two copies of a repeat region R. The correct positions of reads A, B, C and D are shown. The repeat region causes a “fork” in the overlaps, as shown in Figure 1b . The fork is created because read A has a plausible overlap with reads B, C and D, but D does not overlap B and C. We call the overlaps of A with B and D “fork overlaps”. Our goal is to design a method that eliminates the fork overlaps from the list of plausible overlaps, thereby producing a list of overlaps we call “reliable”. In Figure 1b , the only overlap that we would like to call reliable is between reads A

Read the complete text