BACKGROUND
recently the prevalence of high-throughput sequencing technologies has prompted the emergence of a new class of de novo sequence assembler.
this new class of assembler is specialized to deal with the short, non-perfect reads produced by modern high-throughput sequencers such as those produced by the illumina and applied biosystems solid platforms and includes applications such as ssake  <cit> , velvet  <cit> , edena  <cit> , sharcgs  <cit> , vcake  <cit> , allpaths  <cit> , and euler-sr  <cit> .
current short-read assemblers all provide the means of stitching together small fragments of dna sequences to form longer contigs.
common to all short-read assemblers is the concept of bridging overlapping dna fragments, best expressed by de bruijn graphs  <cit> .
while all short-read assemblers share this foundation, algorithms differ from assembler to assembler, resulting in significant runtime and output differences.
high-throughput sequencing technologies produce non-negligible error rates in their sequenced output.
as such, de novo assemblers should be designed to minimize the incorporation of errors during contig extension to ensure that their output is of the highest possible quality.
while assemblers unable to account for error may be able to assemble error-free reads, such assemblers fail when working with real-world, non-perfect data.
our algorithm, qsra , builds directly upon the vcake algorithm.
implemented in c++, we show that qsra not only provides for much faster assembly than vcake, but through the use of quality-values qsra can continue contig extension where vcake cannot, resulting in longer average contig lengths.
we have also implemented the option to output suspected repeated regions to a separate file, aiding in repeat-related analysis.
implementation
material
illumina data generated by shotgun sequencing of the pinus pinaster  and pinus gerardiana  chloroplast genomes were used for test assemblies  <cit> .
pina data consisted of  <dig> , <dig> bases with a reference genome of  <dig>  bases, resulting in an average coverage depth of 479×.
gera <dig> data consisted of  <dig> , <dig> bases with a reference genome of  <dig>  bases, resulting in an average coverage depth of 376×, with both data sets having an input read length of  <dig> bp.
one lane of sequence data from the illumina  <dig> g genome analyzer, generated by shotgun sequencing of the streptococcus suis  bacterial genome, was also used for test assembly.
produced by the s. suis sequencing group at the sanger institute, this illumina data  <cit>  consisted of  <dig> , <dig> bases with the reference genome  <cit>  containing  <dig> , <dig> bases, resulting in an average coverage depth of 49×.
read length in this case was  <dig> bp.
genome coverage estimates were obtained by alignment of the contigs output by the assemblers against the respective reference genome  <cit>  using blat  <cit> .
blat output was analyzed by comparing the total number of bases in the reference genome with the number of genomic bases uniquely "hit" by assembled contigs.
thus, any contig which blat, using the default value of 90% identity, could not match to the appropriate reference genome did not contribute to coverage calculations.
algorithm
after all exact-matching reads, according to the above criteria, have been added to the linked list, qsra computes the total number of matches, accounting for duplicated reads such that each copy of a read counts as matching.
if this number is less than a user-defined value t, qsra proceeds to find all matching reads down to a lower user-defined limit l. if, after this step, t matches are still not found, qsra finds all matching reads down to an overlap of only  <dig> bases, lines 8– <dig> in figure  <dig>
at this point our algorithm makes its first major departure from vcake with one additional and important extension condition.
if t matching sequences are still not found, and the quality-values  option is not being used in the current assembly, then extension on that side of the growing contig is halted.
however, if q-values are being used in the current assembly, qsra will extend the growing contig even if t matches are still not found, as long as a minimum user-defined q-value score, m is met or exceeded at the current over-hanging base position, lines 19– <dig> in figure  <dig>  this allows for extension of contigs in some cases far beyond the vcake algorithm.
next the sequences populating the linked list are considered.
each read represented in the linked list casts a number of votes equal to its multiplicity for which base should be added to the end of the growing contig.
the base with the highest number of votes is then added to the 3' end of the growing contig, as long as the base garners a user-defined minimum percentage, c, of the vote.
if the winning base does not hold c percentage of the vote, or if the number of votes exceeds a user-defined maximum, x, extension is terminated for that side of the growing contig due to assumed sequence repeats.
with qsra sequence repeats can be further analyzed if desired.
when a contig's extension is aborted due to a sequence repeat condition and the user has enabled the printing of repeated regions, r, the suspected repeated region is output to a separate multi-fasta format file.
all reads that cast a vote at least once are removed from the hash-table and prefix-tree data structures.
the growing contig is extended in this way one base at a time until some condition causes the extension to halt.
extension is then performed on the reverse complemented growing contig in the same manner.
when extension is halted on the reverse complemented growing strand, the resulting contig is output to a file in multi-fasta format and a new seed is selected.
this process continues until there are no more reads in the hash-table and prefix-tree.
RESULTS
all tests were conducted on a  <dig>  ghz xeon linux machine with  <dig> gb of ram.
we ran five tests for each of our three datasets, including ssake, vcake, velvet, edena, qsra without q-values, and qsra with q-values, with results shown in table  <dig>  in all cases the minimum contig length considered in analysis was  <dig> + read length, with each application set to output contigs of at least this length.
in this way singletons were not included in analysis, and all applications were tested on the same basis.
five tests were run for each of three data sets, including ssake, vcake, velvet, edena, qsra without q-values, specified simply as qsra in table  <dig>  and qsra with q-values, specified as qsra* in table  <dig>  in addition to the runtime options listed for velvet, each velvet run used a tile size of  <dig> and a coverage cutoff of  <dig>  only contigs were used, discarding unextended singletons, in the calculation of coverage, n <dig>  and n <dig> values.
coverage values were determined though analysis of blat output by comparing the total number of bases in the reference genome with the number of bases uniquely "hit" by the blat alignments with assembled contigs.
thus, any contig which blat, using the default value of 90% identity, could not match to its reference genome did not contribute to coverage calculations.
n <dig> and n <dig> values are equal to the largest contig in the output such that it and all contigs of greater length accounted for 50%/80% of total genome coverage.
for s. suis,  <dig> % of the  <dig> mer illumina reads in the data set matched perfectly to the reference genome, which corresponds to an estimated average error rate per sequence base of  <dig> %.
for assembly of the pina illumina reads we see that assembly with qsra, both with and without q-values, resulted in a drastically shorter running times than vcake, at  <dig> s and  <dig> s respectively, compared to vcake's  <dig> s. assembly with qsra yielded the highest genomic coverage as well, at  <dig> % and  <dig> % with and without q-values respectively.
while edena and velvet yielded the longest individual contigs at  <dig>  bp and  <dig>  bp, qsra yielded the next longest contigs at  <dig>  bp with q-values and  <dig>  bp without q-values.
on the gera <dig> illumina reads, qsra again finished far more quickly than vcake at 641s and 733s as compared to vcake's  <dig> s. again assembly with qsra maintains the highest genomic coverage at  <dig> % and  <dig> %, although in this case velvet yielded the longest single contig at  <dig>  bp, compared to qsra with its longest contig at  <dig> bp.
for the s. suisp data set all applications tested performed very well in overall coverage.
velvet yielded the longest single contig at  <dig>  bp followed by qsra's  <dig>  bp.
qsra finished in roughly half the time as vcake, yielding n <dig> lengths second only to velvet.
CONCLUSIONS
for our tests, edena and velvet generally yielded the longest contigs while qsra generally produced the highest genomic coverage.
qsra was much faster than vcake while implementing the use of q-values, while providing the option to output suspected repeated regions.
qsra is extremely competitive in its longest contig and n50/n <dig> contig lengths output, producing results of similar quality to those of edena and velvet, while finishing in far less time than vcake.
assemblers such as edena and velvet summarize their input reads by constructing a graph which is then processed and traversed in a second step to generate contigs.
this processing results in some information loss as input reads are not considered individually as they are in assemblers such as ssake, vcake, and qsra.
this algorithmic difference is responsible for the trade-off observed here whereby edena and velvet output generally longer but fewer contigs and have lower overall genomic coverage, while ssake, vcake, and qsra output generally a higher number of shorter contigs that, in the case of qsra, result in a higher overall genomic overage.
qsra provides a step closer to the goal of de novo assembly of complex genomes, improving upon the original vcake algorithm by not only drastically reducing runtimes but also by increasing the viability of the assembly algorithm by addition of further error handling capabilities.
availability and requirements
• project name: qsra – quality-value guided short read assembler
• project home page:
• operating system: unix
• programming language: c++
• other requirements: none
• license: free for educational and public use
• any restrictions to use by non-academics: must obtain permission from author for non-academic/non-public use
abbreviations
the following abbreviations have been used: ram: random access memory; gb: gigabyte; ghz: gigahertz.
authors' contributions
dwb coded the qsra algorithm, conducted the analyses, analyzed the data, and drafted the manuscript.
wkw and tcm participated in the design of the study and helped to draft the manuscript.
all authors read and approved the final manuscript.

 recently the prevalence of high-throughput sequencing technologies has prompted the emergence of a new class of de novo sequence assembler. this new class of assembler is specialized to deal with the short, non-perfect reads produced by modern high-throughput sequencers such as those produced by the illumina and applied biosystems solid platforms and includes applications such as ssake, velvet, edena, sharcgs, vcake, allpaths, and euler-sr. current short-read assemblers all provide the means of stitching together small fragments of dna sequences to form longer contigs. common to all short-read assemblers is the concept of bridging overlapping dna fragments, best expressed by de bruijn graphs. while all short-read assemblers share this foundation, algorithms differ from assembler to assembler, resulting in significant runtime and output differences. high-throughput sequencing technologies produce non-negligible error rates in their sequenced output. as such, de novo assemblers should be designed to minimize the incorporation of errors during contig extension to ensure that their output is of the highest possible quality. while assemblers unable to account for error may be able to assemble error-free reads, such assemblers fail when working with real-world, non-perfect data. our algorithm, qsra, builds directly upon the vcake algorithm. implemented in c++, we show that qsra not only provides for much faster assembly than vcake, but through the use of quality-values qsra can continue contig extension where vcake cannot, resulting in longer average contig lengths. we have also implemented the option to output suspected repeated regions to a separate file, aiding in repeat-related analysis. implementation material illumina data generated by shotgun sequencing of the pinus pinaster and pinus gerardiana chloroplast genomes were used for test assemblies. pina data consisted of, bases with a reference genome of bases, resulting in an average coverage depth of 479×. gera data consisted of, bases with a reference genome of bases, resulting in an average coverage depth of 376×, with both data sets having an input read length of bp. one lane of sequence data from the illumina g genome analyzer, generated by shotgun sequencing of the streptococcus suis bacterial genome, was also used for test assembly. produced by the s. suis sequencing group at the sanger institute, this illumina data consisted of, bases with the reference genome containing, bases, resulting in an average coverage depth of 49×. read length in this case was bp. genome coverage estimates were obtained by alignment of the contigs output by the assemblers against the respective reference genome using blat. blat output was analyzed by comparing the total number of bases in the reference genome with the number of genomic bases uniquely "hit" by assembled contigs. thus, any contig which blat, using the default value of 90% identity, could not match to the appropriate reference genome did not contribute to coverage calculations. algorithm after all exact-matching reads, according to the above criteria, have been added to the linked list, qsra computes the total number of matches, accounting for duplicated reads such that each copy of a read counts as matching. if this number is less than a user-defined value t, qsra proceeds to find all matching reads down to a lower user-defined limit l. if, after this step, t matches are still not found, qsra finds all matching reads down to an overlap of only bases, lines 8– in figure at this point our algorithm makes its first major departure from vcake with one additional and important extension condition. if t matching sequences are still not found, and the quality-values option is not being used in the current assembly, then extension on that side of the growing contig is halted. however, if q-values are being used in the current assembly, qsra will extend the growing contig even if t matches are still not found, as long as a minimum user-defined q-value score, m is met or exceeded at the current over-hanging base position, lines 19– in figure this allows for extension of contigs in some cases far beyond the vcake algorithm. next the sequences populating the linked list are considered. each read represented in the linked list casts a number of votes equal to its multiplicity for which base should be added to the end of the growing contig. the base with the highest number of votes is then added to the 3' end of the growing contig, as long as the base garners a user-defined minimum percentage, c, of the vote. if the winning base does not hold c percentage of the vote, or if the number of votes exceeds a user-defined maximum, x, extension is terminated for that side of the growing contig due to assumed sequence repeats. with qsra sequence repeats can be further analyzed if desired. when a contig's extension is aborted due to a sequence repeat condition and the user has enabled the printing of repeated regions, r, the suspected repeated region is output to a separate multi-fasta format file. all reads that cast a vote at least once are removed from the hash-table and prefix-tree data structures. the growing contig is extended in this way one base at a time until some condition causes the extension to halt. extension is then performed on the reverse complemented growing contig in the same manner. when extension is halted on the reverse complemented growing strand, the resulting contig is output to a file in multi-fasta format and a new seed is selected. this process continues until there are no more reads in the hash-table and prefix-tree.  all tests were conducted on a ghz xeon linux machine with gb of ram. we ran five tests for each of our three datasets, including ssake, vcake, velvet, edena, qsra without q-values, and qsra with q-values, with results shown in table in all cases the minimum contig length considered in analysis was + read length, with each application set to output contigs of at least this length. in this way singletons were not included in analysis, and all applications were tested on the same basis. five tests were run for each of three data sets, including ssake, vcake, velvet, edena, qsra without q-values, specified simply as qsra in table and qsra with q-values, specified as qsra* in table in addition to the runtime options listed for velvet, each velvet run used a tile size of and a coverage cutoff of only contigs were used, discarding unextended singletons, in the calculation of coverage, n and n values. coverage values were determined though analysis of blat output by comparing the total number of bases in the reference genome with the number of bases uniquely "hit" by the blat alignments with assembled contigs. thus, any contig which blat, using the default value of 90% identity, could not match to its reference genome did not contribute to coverage calculations. n and n values are equal to the largest contig in the output such that it and all contigs of greater length accounted for 50%/80% of total genome coverage. for s. suis, % of the mer illumina reads in the data set matched perfectly to the reference genome, which corresponds to an estimated average error rate per sequence base of %. for assembly of the pina illumina reads we see that assembly with qsra, both with and without q-values, resulted in a drastically shorter running times than vcake, at s and s respectively, compared to vcake's s. assembly with qsra yielded the highest genomic coverage as well, at % and % with and without q-values respectively. while edena and velvet yielded the longest individual contigs at bp and bp, qsra yielded the next longest contigs at bp with q-values and bp without q-values. on the gera illumina reads, qsra again finished far more quickly than vcake at 641s and 733s as compared to vcake's s. again assembly with qsra maintains the highest genomic coverage at % and %, although in this case velvet yielded the longest single contig at bp, compared to qsra with its longest contig at bp. for the s. suisp data set all applications tested performed very well in overall coverage. velvet yielded the longest single contig at bp followed by qsra's bp. qsra finished in roughly half the time as vcake, yielding n lengths second only to velvet.  for our tests, edena and velvet generally yielded the longest contigs while qsra generally produced the highest genomic coverage. qsra was much faster than vcake while implementing the use of q-values, while providing the option to output suspected repeated regions. qsra is extremely competitive in its longest contig and n50/n contig lengths output, producing results of similar quality to those of edena and velvet, while finishing in far less time than vcake. assemblers such as edena and velvet summarize their input reads by constructing a graph which is then processed and traversed in a second step to generate contigs. this processing results in some information loss as input reads are not considered individually as they are in assemblers such as ssake, vcake, and qsra. this algorithmic difference is responsible for the trade-off observed here whereby edena and velvet output generally longer but fewer contigs and have lower overall genomic coverage, while ssake, vcake, and qsra output generally a higher number of shorter contigs that, in the case of qsra, result in a higher overall genomic overage. qsra provides a step closer to the goal of de novo assembly of complex genomes, improving upon the original vcake algorithm by not only drastically reducing runtimes but also by increasing the viability of the assembly algorithm by addition of further error handling capabilities. availability and requirements • project name: qsra – quality-value guided short read assembler • project home page: • operating system: unix • programming language: c++ • other requirements: none • license: free for educational and public use • any restrictions to use by non-academics: must obtain permission from author for non-academic/non-public use abbreviations the following abbreviations have been used: ram: random access memory; gb: gigabyte; ghz: gigahertz. authors' contributions dwb coded the qsra algorithm, conducted the analyses, analyzed the data, and drafted the manuscript. wkw and tcm participated in the design of the study and helped to draft the manuscript. all authors read and approved the final manuscript. 
since all high-throughput sequencing platforms incorporate errors in their output, short-read assemblers must be designed to account for this error while utilizing all available data. qsra provides a step closer to the goal of de novo assembly of complex genomes, improving upon the original vcake algorithm by not only drastically reducing runtimes but also increasing the viability of the assembly algorithm through further error handling capabilities. qsra is extremely competitive in its longest contig and n50/n contig lengths, producing results of similar quality to those of edena and velvet. new rapid high-throughput sequencing technologies have sparked the creation of a new class of assembler. qsra generally produced the highest genomic coverage, while being faster than vcake.
 new rapid high-throughput sequencing technologies have sparked the creation of a new class of assembler. since all high-throughput sequencing platforms incorporate errors in their output, short-read assemblers must be designed to account for this error while utilizing all available data.  we have designed and implemented an assembler, quality-value guided short read assembler, created to take advantage of quality-value scores as a further method of dealing with error. compared to previous published algorithms, our assembler shows significant improvements not only in speed but also in output quality.  qsra generally produced the highest genomic coverage, while being faster than vcake. qsra is extremely competitive in its longest contig and n50/n contig lengths, producing results of similar quality to those of edena and velvet. qsra provides a step closer to the goal of de novo assembly of complex genomes, improving upon the original vcake algorithm by not only drastically reducing runtimes but also increasing the viability of the assembly algorithm through further error handling capabilities. 