Apr 30, 2010

A parallel algorithm for error correction in high-throughput short-read data on CUDA-enabled graphics hardware

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Haixiang ShiWolfgang Müller-Wittig

Abstract

Emerging DNA sequencing technologies open up exciting new opportunities for genome sequencing by generating read data with a massive throughput. However, produced reads are significantly shorter and more error-prone compared to the traditional Sanger shotgun sequencing method. This poses challenges for de novo DNA fragment assembly algorithms in terms of both accuracy (to deal with short, error-prone reads) and scalability (to deal with very large input data sets). In this article, we present a scalable parallel algorithm for correcting sequencing errors in high-throughput short-read data so that error-free reads can be available before DNA fragment assembly, which is of high importance to many graph-based short-read assembly tools. The algorithm is based on spectral alignment and uses the Compute Unified Device Architecture (CUDA) programming model. To gain efficiency we are taking advantage of the CUDA texture memory using a space-efficient Bloom filter data structure for spectrum membership queries. We have tested the runtime and accuracy of our algorithm using real and simulated Illumina data for different read lengths, error rates, input sizes, and algorithmic parameters. Using a CUDA-enabled mass-produced GPU (available f...Continue Reading

  • References20
  • Citations18
  • References20
  • Citations18

Citations

Mentioned in this Paper

Computer Graphics
Sequencing
Sequence Determinations, DNA
GenBank
Genome Sequencing
Shotgun Sequencing
Computers, Digital
Computational Molecular Biology
Determination, Sequence Homology
DNA Sequence

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Bone Marrow Neoplasms

Bone Marrow Neoplasms are cancers that occur in the bone marrow. Discover the latest research on Bone Marrow Neoplasms here.

IGA Glomerulonephritis

IgA glomerulonephritis is a chronic form of glomerulonephritis characterized by deposits of predominantly Iimmunoglobin A in the mesangial area. Discover the latest research on IgA glomerulonephritis here.

Cryogenic Electron Microscopy

Cryogenic electron microscopy (Cryo-EM) allows the determination of biological macromolecules and their assemblies at a near-atomic resolution. Here is the latest research.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

LRRK2 & Immunity During Infection

Mutations in the LRRK2 gene are a risk-factor for developing Parkinson’s disease. However, LRRK2 has been shown to function as a central regulator of vesicular trafficking, infection, immunity, and inflammation. Here is the latest research on the role of this kinase on immunity during infection.

Antiphospholipid Syndrome

Antiphospholipid syndrome or antiphospholipid antibody syndrome (APS or APLS), is an autoimmune, hypercoagulable state caused by the presence of antibodies directed against phospholipids.

Meningococcal Myelitis

Meningococcal myelitis is characterized by inflammation and myelin damage to the meninges and spinal cord. Discover the latest research on meningococcal myelitis here.

Alzheimer's Disease: MS4A

Variants within membrane-spanning 4-domains subfamily A (MS4A) gene cluster have recently been implicated in Alzheimer's disease by recent genome-wide association studies. Here is the latest research.