Format

Send to

Choose Destination
Bioinformatics. 2020 Mar 13. pii: btaa179. doi: 10.1093/bioinformatics/btaa179. [Epub ahead of print]

Apollo: A Sequencing-Technology-Independent, Scalable, and Accurate Assembly Polishing Algorithm.

Author information

1
Department of Computer Science, ETH Zurich, Zurich, Switzerland.
2
Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA.
3
Department of Computer Engineering, Bilkent University, Ankara, Turkey.

Abstract

MOTIVATION:

Third-generation sequencing technologies can sequence long reads that contain as many as 2 million base pairs (bp). These long reads are used to construct an assembly (i.e., the subject's genome), which is further used in downstream genome analysis. Unfortunately, third-generation sequencing technologies have high sequencing error rates and a large proportion of bps in these long reads are incorrectly identified. These errors propagate to the assembly and affect the accuracy of genome analysis. Assembly polishing algorithms minimize such error propagation by polishing or fixing errors in the assembly by using information from alignments between reads and the assembly (i.e., read-to-assembly alignment information). However, current assembly polishing algorithms can only polish an assembly using reads either from a certain sequencing technology or from a small assembly. Such technology-dependency and assembly-size dependency require researchers to 1) run multiple polishing algorithms and 2) use small chunks of a large genome to use all available read sets and polish large genomes, respectively.

RESULTS:

We introduce Apollo, a universal assembly polishing algorithm that scales well to polish an assembly of any size (i.e., both large and small genomes) using reads from all sequencing technologies (i.e., second- and third-generation). Our goal is to provide a single algorithm that uses read sets from all available sequencing technologies to improve the accuracy of assembly polishing and that can polish large genomes. Apollo 1) models an assembly as a profile hidden Markov model (pHMM), 2) uses read-to-assembly alignment to train the pHMM with the Forward-Backward algorithm, and 3) decodes the trained model with the Viterbi algorithm to produce a polished assembly. Our experiments with real read sets demonstrate that Apollo is the only algorithm that 1) uses reads from any sequencing technology within a single run and 2) scales well to polish large assemblies without splitting the assembly into multiple parts.

SUPPLEMENTARY INFORMATION:

Supplementary data is available at Bioinformatics online. online.

AVAILABILITY:

Source code is available at https://github.com/CMU-SAFARI/Apollo.

Supplemental Content

Full text links

Icon for Silverchair Information Systems
Loading ...
Support Center