2013-05-10

Since the read lengths of high throughput sequencing (HTS) technologies are short, de novo assembly which plays significant roles in many applications remains a great challenge. Most of the state-of-the-art approaches base on de Bruijn graph strategy and overlap-layout strategy. However, these approaches which depend on k-mers or read overlaps do not fully utilize information of paired-end and single-end reads when resolving branches. Since they treat all single-end reads with overlapped length larger than a fix threshold equally, they fail to use the more confident long overlapped reads for assembling and mix up with the relative short overlapped reads. Moreover, these approaches have not been special designed for handling tandem repeats (repeats occur adjacently in the genome) and they usually break down the contigs near the tandem repeats. We present PERGA (Paired-End Reads Guided Assembler), a novel sequence-reads-guided de novo assembly approach, which adopts greedy-like prediction strategy for assembling reads to contigs and scaffolds using paired-end reads and different read overlap size ranging from Omax to Omin to resolve the gaps and branches. By constructing a decision model using machine learning approach based on branch features, PERGA can determine the correct extension in 99.7% of cases. When the correct extension cannot be determined, PERGA will try to extend the contig by all feasible extensions and determine the correct extension by using look-ahead approach. Many difficult-resolved branches are due to tandem repeats which are close in the genome. PERGA detects such different copies of the repeats to resolve the branches to make the extension much longer and more accurate. We evaluated PERGA on both Illumina real and simulated datasets ranging from small bacterial genomes to large human chromosome, and it constructed longer and more accurate contigs and scaffolds than other state-of-the-art assemblers. PERGA can be freely downloaded at https://github.com/hitbio/PERGA.

Zhu, X, Leung, HCM, Chin, FYL, Yiu, SM, Quan, G, Liu, B, Wang, Y. (2013). Data from: PERGA: A Paired-End Read Guided De Novo Assembler for Extending Contigs Using SVM and Look Ahead Approach. [Data File]. The authors confirm that all data underlying the findings are fully available without restriction. The simulated reads data are available from https://github.com/hitbio/PERGA. The E.coli real short reads data can be downloaded from http://bix.ucsd.edu/projects/singlecell/nbt_data.html. The S.pombe real short reads data are available from NCBI website http://www.ncbi.nlm.nih.gov/sra/?term=ERX174934. The human chromosome 14 real data are available from GAGE project http://gage.cbcb.umd.edu/data.
Click on “Linked Publications” to access the publication and access supporting information on figshare at https://figshare.com/articles/PERGA_A_Paired_End_Read_Guided_De_Novo_Assembler_for_Extending_Contigs_Using_SVM_and_Look_Ahead_Approach/1256990

handling tandem

decision model

contig

PERGA

overlap size

genome

hts

svm

assembly approach

branch features

throughput sequencing

approaches base

Bruijn graph strategy

extension