GAML: genome assembly by maximum likelihood
- PDF / 1,244,173 Bytes
- 10 Pages / 595.276 x 793.701 pts Page_size
- 60 Downloads / 226 Views
Open Access
RESEARCH
GAML: genome assembly by maximum likelihood Vladimír Boža, Broňa Brejová and Tomáš Vinař*
Abstract Background: Resolution of repeats and scaffolding of shorter contigs are critical parts of genome assembly. Modern assemblers usually perform such steps by heuristics, often tailored to a particular technology for producing paired or long reads. Results: We propose a new framework that allows systematic combination of diverse sequencing datasets into a single assembly. We achieve this by searching for an assembly with the maximum likelihood in a probabilistic model capturing error rate, insert lengths, and other characteristics of the sequencing technology used to produce each dataset. We have implemented a prototype genome assembler GAML that can use any combination of insert sizes with Illumina or 454 reads, as well as PacBio reads. Our experiments show that we can assemble short genomes with N50 sizes and error rates comparable to ALLPATHS-LG or Cerulean. While ALLPATHS-LG and Cerulean require each a specific combination of datasets, GAML works on any combination. Conclusions: We have introduced a new probabilistic approach to genome assembly and demonstrated that this approach can lead to superior results when used to combine diverse set of datasets from different sequencing technologies. Data and software is available at http://compbio.fmph.uniba.sk/gaml. Keywords: Genome assembly, Maximum likelihood, Simulated annealing, De Bruijn graphs, Next generation sequencing Background The second and third generation sequencing technologies have dramatically decreased the cost of sequencing. Nowadays, we have a surprising variety of sequencing technologies, each with its own strengths and weaknesses. For example, Illumina platforms are characteristic by low cost and high accuracy, but the reads are short. On the other hand, Pacific Biosciences offer long reads at the cost of quality and coverage. In the meantime, the cost of sequencing was brought down to the point, where it is no longer a sole domain of large sequencing centers; even small labs can experiment with cost-effective genome sequencing. As a result, it is not realistic to assume an existence of a single standard protocol for sequencing genomes of a particular size. In this paper, we propose a framework for genome assembly that allows flexible *Correspondence: [email protected] Faculty of Mathematics, Physics, and Informatics, Comenius University, Mlynská dolina, 842 48 Bratislava, Slovakia
combination of datasets from different technologies in order to harness their individual strengths. Modern genome assemblers are usually based either on the overlap–layout–consensus framework (e.g. Celera [1], SGA [2]), or on de Bruijn graphs (e.g. Velvet [3], ALLPATHS-LG [4]). Both approaches can be seen as special cases of a string graph [5], in which we represent sequence fragments as vertices, while edges represent possible adjacencies of fragments in the assembly. A genome assembly is simply a set of walks through this graph. The main diffe
Data Loading...
