-
Notifications
You must be signed in to change notification settings - Fork 82
SGA Design
SGA implements a set of assembly algorithms based on the FM-index. As the FM-index is a compressed data structure, the algorithms are very memory efficient.
An SGA assembly has three distinct phases. The first phase corrects base calling errors in the reads. The second phase assembles contigs from the corrected reads. The third phase uses paired end and/or mate pair data to build scaffolds from the contigs. Example real-data assemblies can be found here.
The first stage of the assembly. An FM-index of the sequence reads is constructed, then base calling errors are identified by finding low-frequency k-mers in the reads. The output from the error corrector is a set of FASTQ files containing the corrected read sequences.
An FM-index of the corrected sequence reads is constructed. Duplicate reads, and low-quality reads after correction, are found and discarded with the sga filter subprogram. For large genomes, the sga fm-merge program can be used to merge together reads that can be unambiguously assembled. sga overlap computes the structure of the string graph and contigs are built using sga assemble.
The scaffolding module of sga begins by re-aligning reads to the contigs built in the previous step. The copy number of each contig, and distances between contigs, are estimated from the resulting BAM files and used as input to sga scaffold. The output of sga scaffold is passed to sga scaffold2fasta which produces a FASTA file of the resulting scaffold sequences.