Performance of genetic programming optimised Bowtie2 on genome comparison and analytic testing (GCAT) benchmarks.

Langdon WB. · 2015

Read Performance of genetic programming optimised Bowtie2 on genome comparison and analytic testing (GCAT) benchmarks. by Langdon WB. (2015) 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/europmc-pmc4304608.txt.

Introduction

W B Langdon reports test results for a version of the Bowtie2 DNA alignment tool that was sped up by genetic programming. The paper appeared in BioData Mining in 2015, and Langdon writes as sole author. Aligning millions of short DNA reads to a reference genome is a daily bottleneck in genetics, and hand tuning the software for each new machine is slow skilled work.

An automated evolution method had earlier produced a Bowtie2 variant much faster on one scanner's output. Here that variant faces standard synthetic benchmarks, alone and with its gains ported into the current release. The tests check whether machine made speedups hold up beyond the data they were bred on.

Catalog record

CREATORLangdon WB.
YEAR2015
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC4304608

Browse the full library · About the Tower of Babel

Full text

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

Performance of genetic programming optimised Bowtie2 on genome comparison and analytic testing (GCAT) benchmarks By W B Langdon Published in: BioData Mining DOI: 10.1186/s13040-014-0034-0 ABSTRACT Background Genetic studies are increasingly based on short noisy next generation scanners. Typically complete DNA sequences are assembled by matching short NextGen sequences against reference genomes. Despite considerable algorithmic gains since the turn of the millennium, matching both single ended and paired end strings to a reference remains computationally demanding. Further tailoring Bioinformatics tools to each new task or scanner remains highly skilled and labour intensive. With this in mind, we recently demonstrated a genetic programming based automated technique which generated a version of the state-of-the-art alignment tool Bowtie2 which was considerably faster on short sequences produced by a scanner at the Broad Institute and released as part of The Thousand Genome Project. Results Bowtie2 GP and the original Bowtie2 release were compared on bioplanet’s GCAT synthetic benchmarks. Bowtie2 GP enhancements were also applied to the latest Bowtie2 release (2.2.3, 29 May 2014) and retained both the GP and the manually introduced improvements. Conclusions On both singled ended and paired-end synthetic next generation DNA sequence GCAT benchmarks Bowtie2GP runs up to 45% faster than Bowtie2. The lost in accuracy can be as little as 0.2–0.5% but up to 2.5% for longer sequences. BACKGROUND “Next generation sequencing (NGS) technology has become the de facto indispensable tool to study genomics and epigenomics in recent years” [1]. Although NGS DNA scanners can generate in the region of a billion DNA sequences per run, each sequence is only a few hundred base pairs (bp) long [2]. Typically each sequence is aligned against an existing reference genome. While in many cases DNA sequences match the reference exactly, since next generation scanners are inherently noisy, it is common practise to scan the target sample three times. Consistent differences between NGS sequences and the reference genome may indicate mutations in the sample. The 1000 Genomes Project used next generation scanners to identify 15 million single base changes (SNPs) and more complex mutations [3,4]. Many genomes contain repeated DNA sequences [5], thus a short DNA sequence may match a reference genome more than once. To extend the usefulness of existing scanners, they can be used to generate “paired-end” sequences, in which both ends of longer DNA strands are sequenced in the normal way but the connecting part is not [6]. The length of the unsequenced region is known only approximately. Typically it is in the region of 500 bp. If one end lies in a repeated sequence, the other end can be used. However even if both ends lie in repeated sequences, typically knowing approximately how far apart the two ends are is sufficient to remove the ambiguity of both ends matching multiple times. Matching (also known as mapping) biological sequences is essentially a computational task. Indeed it remains the life blood of Bioinformatics. BLAST [7] remains the gold standard computer program for approximate biological string matching. However it is usually considered far too slow to use with the huge volume of data generated by NextGen scanners. Bowtie [8] was the first fast program able to deal with NextGen DNA sequences and able to compress the human genome into less than 4 GBytes. (Fitting into four gigabytes enabled Bowtie to run on typical desktop computers then available.) However Bowtie is limited in the types of mutation it can deal with and so it was re-written to give the more functional Bowtie2 [9]. Perhaps surprisingly some of the best programs are publicly funded open source and freely available rather than commercial. E.g. BWA [10] and Bowtie2. Introduction Genetic programming (GP) [11,12] is one of a family of computer techniques [13-15] which use Darwin’s theory of evolution of species by natural selection [16] by applying survival of the fitness to an artificial population inside the computer. Typically the programmer provides an external fitness function which is used to determine the fitness of individuals in the population and so who survives and has children. Children are created by applying operations analogous to mutation and recombination to their parents. In the case of GP the population contains a species of computer programs. Special mutation and recombination operations are used which ensure the children are syntactically correct programs and their fitness is calculated by running them on input data from the problem and assessing the quality of their answers. In the http://www.cs.ucl.ac.uk/staff/W.Langdon/gismo/ Gismo project instead of evolving complete programs, we used GP to evolve a population of patches to Bowtie2. GP was used in combination with other search based software engineering techniques [17] to automatically tailor Bowtie2, giving a version which runs considerably faster than the original released code on “single ended” short (36 bp) DNA sequences produced by the Broad Institute’s Illumina Genome Analyzer II Solexa scanner. The goal was to find matches in the human genome faster without unduly sacrificing the quality of the matches. On out-of-sample Solexa sequences on average it runs more than 70 times faster than the original release of Bowtie2 and finds very slightly better matches [18]. While we would normally advocate re-optimising the Bowtie2 C++ code for new circumstances, we show the optimised version can also process DNA sequences from other sources. On paired-end data from the UCL http://www.ucl.ac.uk/cancer/ Cancer Institute human blood studies we found Bowtie2 GP not only ran faster than Bowtie2 but was also more than four times faster than the Bioinformatics sequencing tool (BWA [10]) currently used by the Cancer Institute, takes less memory and yet finds similar matches in the human genome [19]. Next we submitted 4 versions of Bowtie2 to the widely respected GCAT [20] synthetic NextGen benchmarks (the original Bowtie2 and the current release and GP updated versions of both). Unlike the real data supplied by the Cancer Institute, GCAT has the advantage that the sequences have been prepared against a reference genome and so have both defined noise characteristics and known ground truth. Since the correct mapping is known, GCAT can readily calculate the fraction which are correct. METHOD The DNA test sequences for eight GCAT benchmarks were down loaded via the GCAT eb interface at http://www.bioplanet.com/gcat/ in fastq format. The benchmarks cover sequences of lengths 100 base pairs, 150 bp, 250 bp and 400 bp, for both paired end and single ended small-indel tests. There are two files for each of the paired end and one _1.fastq file for each single ended benchmarks. Making a total of 41 509 741 sequences, occupying 25 gigabytes. As recommended by GCAT, pre-built Bowtie2 index files for the human genome (hg19, GRCh37 Genome Reference Consortium Human Reference 37 (GCA_000001405.1)) were down loaded from ftp://ftp.ccb.jhu.edu/pub/data/bowtie2_indexes/hg19.zip Decompressed the.bt2 files occupy 4 GB in total. As recommended by GCAT, samtools was used to convert Bowtie2 sam output to the bam format used by GCAT. Pre built 64-bit executable programs for Linux samtools were obtained from SourceForge (http://sourceforge.net/projects/samtools/files/samtools/1.0/ We used four versions of Bowtie2; two from Ben Langmead and two after GP improvement. The original release of Bowtie2 (version 2.0.0 beta, 16 Oct 2011) has been updated automatically by genetic programming to give Bowtie2 GP [18]. (Bowtie2 GP is available via http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/gp-code/bowtie2gp W.Langdon/ftp/gp-code/bowtie2gp.) The seven changes made by genetic programming

Read the complete text