BACKGROUND
de novo whole-genome shotgun sequencing requires three general steps: an initial sequencing step in which the target genome is redundantly sampled at random, producing reads via sequencing; assembly of the reads into a draft sequence; and finally, finishing and annotation of the genome.
the second step in particular leads to numerous algorithmic challenges, and a number of approaches have been pioneered to deal with increasingly short reads and/or large target sequences as the capacity of sequencing facilities increases.
in general, two algorithmic approaches are currently employed for genome assembly.
the first, which we call the overlap-contig-consensus  approach, is utilized in assemblers such as the celera assembler  <cit> , arachne  <cit> , atlas  <cit> , and more recently cabog  <cit>  and edena  <cit> .
implementations of occ first calculate the overlaps between all pairs of reads, then use the overlap information to produce contigs, and finally generate the consensus sequence for the contigs.
the second, which we call the de bruijn approach, was first adopted from prior algorithmic work on sequencing by hybridization in the euler-db  <cit>  assembler.
this approach and related approaches have been used in assemblers such as euler-sr  <cit> , allpaths  <cit> , and velvet  <cit> .
the de bruijn approach creates some form of "k-mer graph" from the reads and produces an assembly by transforming and traversing the graph.
it is still unclear whether either of these paradigms is consistently superior to the other.
but in general the success of the de bruijn approach relies upon robust error detection in the reads to be practical, while the occ approach requires fast and accurate overlap calculations.
the latter problem is the focus of this work.
the occ approach is best described by thinking of the target genome as a large interval, and the reads as being sub-intervals of the genome.
this picture is oversimplified because it does not model the presence of errors and polymorphisms--particularly indels and structural polymorphisms--within the input reads, but is sufficient to introduce the general concept.
dealing with the presence of substantial polymorphisms in the context of occ has been addressed in other work  <cit> .
it is worth noting a few properties of the occ approach.
first, if the true overlaps between the reads were somehow known exactly, then contig formation on this ideal data set would be equivalent to interval graph realization, a trivial problem.
the implication is that overlapping is the more critical step.
second, overlapping reads should have a perfect--or nearly-perfect in the presence of sequencing errors--sequence alignment between their overlapping regions, and this observation is the fundamental basis for overlap detection algorithms.
finally, when overlap detection algorithms make errors, the most common and most damaging are false positives due to the presence of repeat sequences that create good alignments between reads even though those reads do not represent overlapping intervals on the genome.
incorporating such overlaps into contigs produces mis-assemblies.
because comparing all pairs of reads for overlaps is a time-consuming process in large data sets, developers of overlapping methods have focused on efficient methods for finding alignments in large sequence collections.
they have then generally equated the resulting alignments with the overlap relationships between the reads, despite the fact that the presence of an alignment between the ends of two reads is necessary but not sufficient evidence for an overlap.
when this problem has been considered, it has been addressed with simple heuristics.
for example, the celera assembler attempts to avoid repeat-induced overlaps by screening for known repeat sequences, and cabog and the umd overlapper  <cit>  attempt to reduce false positives with heuristic selection of "good" k-mers that are used to seed  or confirm  overlaps.
since adequate solutions exist for fast alignment searching, for example the algorithm of rasmussen  <cit> , this work focuses specifically on answering the critical follow-up question: given that an alignment exists between two reads, do they really overlap?
in contrast to prior work, this question is approached as a formal classification problem.
alignment features are defined and classifiers such as c <dig>  decision tree, naive bayes and random forest are trained and employed within the weka framework  <cit>   to label overlaps as either true or false.
we show that by culling out the false overlaps and thus providing an overlap set that is closer to ideal, we are able to achieve longer contigs that cover a larger percentage of the genome.
finally, yet perhaps most importantly, since large-scale sequencing and finished genomes are now ubiquitous, we show how we can leverage previous, related sequencing projects, if available, in the de novo assembly pipeline.
while, other comparative assemblers, such as amoscmp  <cit>  map the reads to a single reference genome, we show how multiple reference genome sequences can be used to help assemble genomes.
rather than produce a whole new genome assembler, we demonstrate our method by introducing it as a module into minimus  <cit> , which is part of the modular open-source assembler  project.
although minimus is not as sophisticated as some other assemblers, amos is notable for being well-engineered and specifically designed to accept external modules and is thus an ideal test vehicle.
RESULTS
evaluation of  <dig> reads from e. coli
overlap statistics
to determine if classification of overlaps can improve the assembly of sequencing reads,  <dig>  sequencing reads from salmonella enterica serovar typhi strain e <dig> were used to build training models within the weka framework, and  <dig>  reads from escherichia coli strain k <dig> substrain mg <dig> were used as a test set to assemble.
the salmonella reads represented an approximately 8× coverage of the genome, while the e. coli reads represented an 18× coverage.
reads from both strains were mapped to their respective genomes to determine the ground truth in regards to whether any predicted overlaps were true or false overlaps.
because the completed genome for strain e <dig> was not available, the s. enterica serovar typhi ty <dig> genome, which shares approximately 96% identity with the e <dig> reads , was used instead.
the amos hash-overlap  <cit>  program was used to identify potential overlaps.
various statistics for these overlaps were calculated as described in the methods.
these statistics included the percent mismatch within the overlap, the first, second, and third quartile k-mer frequencies, and a comparative genomics score.
the quartile frequencies were derived by taking each k-mer within an overlap and calculating a normalized frequency of the k-mer within all reads.
these frequencies were sorted from low to high, and the value of the frequency at each quartile of the distribution of frequencies was calculated.
the distributions of these statistics as a function of the percentage of overlaps were calculated for these features within e. coli mg <dig> to show that in fact these features could partially discriminate true from false overlaps.
as a percentage of total overlaps within the true or false categories, the false overlaps had a larger tail for the percent mismatch score .
since there were a large number of true overlaps compared to false overlaps , the total number of true overlaps with having 1% to 2% mismatches was still higher than false overlaps .
the k-mer distributions are shown in figure 1c-e. as expected, false overlaps tended to have a greater k-mer frequency.
to see if reads from false overlaps tended to be in repetitive parts of the genome, blat  <cit> , with a minimum score  of  <dig>  was used to determine the number of times each read mapped to the reference genome.
reads from true overlaps mapped on average  <dig>  times to the reference genome, while reads from false overlaps mapped on average  <dig>  to the reference genome.
finally a comparative genomics score was generated by mapping the reads to a set of related e. coli genomes .
a positive score was generated when the top match of each read mapped to the same location within a genome.
a negative score was generated when the top match of each read was not in the same location within a genome.
see methods for a detailed description of the comparative genomics score.
classification accuracy
as true and false overlaps had different distributions for the features that were tested, we next wanted to see if these features could be used to train classifiers that could be used to predict true and false overlaps.
the accuracy of various machine learning algorithms in distinguishing true and false overlaps was explored.
for the results shown in table  <dig>  both comparative and non-comparative features were used.
salmonella reads were used to generate the training models used below, and e. coli reads were used as the test set.
for the comparative score, genomes with less than 91% identity to salmonella ty <dig> or e. coli mg <dig> were used.
accuracy was defined as the number of correctly predicted overlaps , divided by the total number of overlaps.
the false positive rate was defined as the number of overlaps incorrectly predicted as positive, divided by the total number of actual false overlaps.
the false negative rate was defined as the number of overlaps incorrectly predicted as false divided by the total number of actual true overlaps.
the j <dig> classifier had the highest accuracy  and the second lowest false positive rate .
the naïve bayes classifier with default parameters produced the lowest false postive rate  but had the highest false negative rate of the machine learning classifiers .
using kernel estimation with naïve bayes improved the accuracy of the classifier and had the lowest false negative rate.
confusion matrices for the classifiers are shown in additional file  <dig>  tables s <dig> and s <dig>  one example decision tree for the j <dig> classifier using both comparative and non-comparative data is shown in additional file  <dig>  table s <dig>
1accuracy is defined as the number of true positive and true negative overlaps divided by the total number of overlaps
2the false positive rate is defined as the number of false positive overlaps divided by the number of false overlaps
3the false negative rate is defined as the number of false negative overlaps divided by the number of true overlaps
4naïvebayes with kernel estimation
we wanted to compare the accuracy of our classifier with other methods of curating overlaps, which are typically rule-based.
the latest version of the umd overlapper program  <cit>  uses a simple rule involving k-mer frequencies to label overlaps as reliable and unreliable.
although this classification is not intended to be utilized for labeling overlaps as strictly true or false, it is similar in spirit, and we evaluated how well the reliable and unreliable categories aligned to true and false overlaps respectively .
the overall accuracy of the reliability labeling was only  <dig> %.
the false positive rate was  <dig> % and the false negative rate was  <dig> %.
assembly of e. coli sequencing reads
the features from the s. typhi training set were used to generate several training models using classifiers such as j <dig>  naïve bayes and random forest within the weka framework.
overlaps from the e. coli reads were generated and classified using the training models.
after removal of overlaps predicted to be false, the reads were assembled using minimus.
the n <dig> score and the percentage of the reference genome matched by contigs were calculated for each assembly .
the n <dig> score was defined as the maximum contig size where all contigs of that size and larger covered 50% of the genome.
a higher n <dig> score generally represents the presence of larger contigs and thus a better assembly of the reads.
as a control, we first assembled e. coli reads without classification and removal of overlaps predicted to be false.
this assembly had an n <dig> score of  <dig>  and  <dig> % of the reference genome was matched.
while several classifiers were tested, including naïvebayes and random forest, the j <dig> classifier generally, but not always, produced better assembly results based on n <dig> scores and the percentage of the reference genome matched.
we also attempted to use support vector machines  within weka, but the classifier failed to finish due to the large number of overlaps involved.
the results presented here represent the values from the j <dig> classification.
the first set of training models were built using the non-comparative features such as mismatch percentage and the k-mer frequencies.
the j <dig> model produced an n <dig> size  <dig>  and a percent genome matched of  <dig> %.
the next model to be analyzed was built using comparative features alone.
for generating the comparative score within the test set, we excluded those strain that were highly similar  to the test strain .
by using this compartive score alone, the assembly produced contigs with an n <dig> score of  <dig>  and a percent match to the reference genome of  <dig> %.
assembling the reads using both the comparative and non-comparative features yielded an assembly with an n <dig> score of  <dig>  and a percent match to the reference genome of  <dig> %.
if we reduced the allowable strains for the comparative feature to those less than 91% identity, the n <dig> score and percent match for the comparative features alone dropped to  <dig>  and  <dig> %.
using both comparative and non-comparative features increased these values to  <dig>  and  <dig> %, respectively.
in addition to using the n <dig> statistic, we examined the n statistic for a range of n with several of the assemblies .
again, the assembly using both comparative  and non-comparative features provided the best results for most of the values of n between  <dig> and  <dig>  additional file  <dig>  figure s <dig> shows the range of n statistics for assemblies using genomes <97% identical.
for some genome sequencing projects, there may not be a large number of related genomes, as there are for e. coli and salmonella.
therefore, the assembly was repeated using only two related genomes for the training and test set.
for salmonella ty <dig>  s. enterica serovar paratyphi strain atcc <dig>  and s. enterica serovar typhimurium lt <dig>  were used as related genomes.
for the mg <dig> test assembly, e. coli strains atcc <dig>  and e24377a  were used as related genomes.
for the j <dig> classifier the n <dig> score was  <dig>  and the percentage of the reference genome matched by the contigs was  <dig> %.
if only ty <dig> for salmonella and atcc <dig> for e. coli were used as related genomes, the n <dig> score for j <dig> decreased to  <dig>  and the percentage of the reference genome matched fell to  <dig> .
these results suggest that there does not need to be a large number of related genomes required for comparisons.
see additional file  <dig>  figure s <dig> for a graph of these values.
analysis of assembly quality
dnadiff was used to identify gross mis-assemblies of the e. coli sequencing reads  <cit> .
we focused on the assembly using non-comparative features combined with the comparative feature using strains less than 97% identity.
dnadiff reported two potential misjoins and a single tandem deletion for both the uncorrected and corrected assemblies.
as a qualitative view of the assemblies, we used mauve  <cit>  to align assembled contigs that had been ordered by snapper  <cit>  to the finished reference genome.
figure  <dig> shows the alignment of the uncorrected .
figure 4a shows the uncorrected assembly, while 3b shows the assembly after overlaps predicted to be false by the j <dig> classifier were removed.
for both 3a and 3b, the assembled contigs are shown mapped to the reference sequence.
contig boundaries are shown by vertical red bars.
different colored blocks represent regions where contigs are in the correct order.
breaks in the correct order of the contigs with respect to the reference genome are shown by the boundaries between colored block, and by the crossing colored lines.
while there are several cases of contigs not being in the correct order , manual inspection of the breaks show that these occur in repetitive regions and do not represent true errors, only differences between alignment algorithms of snapper and mauve.
we were not able to detect any gross mis-assemblies from the alignments.
evaluation of sanger reads from s. aureus
to determine if classification of overlaps could be applied to other types of data sets, we next analyzed sanger reads from staphylococcus aureus.
reads from strain jh <dig> were used as a training set and reads from strain jh <dig> were used in the test set.
both sets of reads represented an approximately 9× coverage of their respective genomes.
the assembly of jh <dig> using uncorrected overlaps produced contigs with an n <dig> score of  <dig>  that matched  <dig> % of the reference genome .
using non-comparative features produced little improvement .
with comparative feature using all s. aureus strains except jh <dig> and jh <dig>  the assembly was improved , while including non-comparative features reduced the assembly quality slightly .
however when only strains with less than 94% identity to jh <dig> and jh <dig> were used for the comparative score, the results of using both non-comparative and comparative features were better than comparative features alone .
the a plot of the n statistic for range of n is shown in additional file  <dig>  figure s <dig>
CONCLUSIONS
by providing a more accurate approximation of the true overlap structure of the input reads, overlap classification can simplify the task of contig construction and thereby create superior assemblies.
in particular, the addition of information from related genomes strengthens the quality of the assembly, without sacrificing the flexibility of the de novo framework for a purely comparative assembly process with a single reference genome such as provided by amoscmp  <cit> .
use of related genomes can potentially be generalized to other aspects of de novo assembly, including the de bruijn approach where this information can be used to resolve pairs of branches.
from the results shown here, if highly similar genomes are available, a purely comparative approach will likely yield better results.
however, if these sequences are not available, using a machine learning approach using non-comparative and comparative features from more distantly related reference genomes can improve sequence assembly.
the overlap classification implementation described here was tested in a rather simple genome assembler, and may produce a smaller percentage improvement of the n <dig> length if placed in more sophisticated assemblers.
on the other hand, the bacterial genomes utilized as test cases are not particularly repetitive; it is hypothesized that the results could be even stronger in repeat-rich genomes.
in our experiments, the size of the training set did not have an impact on the results  , allowing the use of smaller training sets than test sets.
once trained, the decision tree can be quickly applied to new overlaps, and thus the computational time taken by the overlap correction module was in line with other modules in the assembly process.
the alignment statistics should be computed during the overlap process to maximize efficiency and the reads must be searched for high-quality hits to reference genome, but neither of these presents an excessive computational burden compared to other phases of genome assembly.
it should therefore be possible to apply overlap correction to larger genomes.

 de novo whole-genome shotgun sequencing requires three general steps: an initial sequencing step in which the target genome is redundantly sampled at random, producing reads via sequencing; assembly of the reads into a draft sequence; and finally, finishing and annotation of the genome. the second step in particular leads to numerous algorithmic challenges, and a number of approaches have been pioneered to deal with increasingly short reads and/or large target sequences as the capacity of sequencing facilities increases. in general, two algorithmic approaches are currently employed for genome assembly. the first, which we call the overlap-contig-consensus approach, is utilized in assemblers such as the celera assembler, arachne, atlas, and more recently cabog and edena. implementations of occ first calculate the overlaps between all pairs of reads, then use the overlap information to produce contigs, and finally generate the consensus sequence for the contigs. the second, which we call the de bruijn approach, was first adopted from prior algorithmic work on sequencing by hybridization in the euler-db assembler. this approach and related approaches have been used in assemblers such as euler-sr, allpaths, and velvet. the de bruijn approach creates some form of "k-mer graph" from the reads and produces an assembly by transforming and traversing the graph. it is still unclear whether either of these paradigms is consistently superior to the other. but in general the success of the de bruijn approach relies upon robust error detection in the reads to be practical, while the occ approach requires fast and accurate overlap calculations. the latter problem is the focus of this work. the occ approach is best described by thinking of the target genome as a large interval, and the reads as being sub-intervals of the genome. this picture is oversimplified because it does not model the presence of errors and polymorphisms--particularly indels and structural polymorphisms--within the input reads, but is sufficient to introduce the general concept. dealing with the presence of substantial polymorphisms in the context of occ has been addressed in other work. it is worth noting a few properties of the occ approach. first, if the true overlaps between the reads were somehow known exactly, then contig formation on this ideal data set would be equivalent to interval graph realization, a trivial problem. the implication is that overlapping is the more critical step. second, overlapping reads should have a perfect--or nearly-perfect in the presence of sequencing errors--sequence alignment between their overlapping regions, and this observation is the fundamental basis for overlap detection algorithms. finally, when overlap detection algorithms make errors, the most common and most damaging are false positives due to the presence of repeat sequences that create good alignments between reads even though those reads do not represent overlapping intervals on the genome. incorporating such overlaps into contigs produces mis-assemblies. because comparing all pairs of reads for overlaps is a time-consuming process in large data sets, developers of overlapping methods have focused on efficient methods for finding alignments in large sequence collections. they have then generally equated the resulting alignments with the overlap relationships between the reads, despite the fact that the presence of an alignment between the ends of two reads is necessary but not sufficient evidence for an overlap. when this problem has been considered, it has been addressed with simple heuristics. for example, the celera assembler attempts to avoid repeat-induced overlaps by screening for known repeat sequences, and cabog and the umd overlapper attempt to reduce false positives with heuristic selection of "good" k-mers that are used to seed or confirm overlaps. since adequate solutions exist for fast alignment searching, for example the algorithm of rasmussen, this work focuses specifically on answering the critical follow-up question: given that an alignment exists between two reads, do they really overlap? in contrast to prior work, this question is approached as a formal classification problem. alignment features are defined and classifiers such as c decision tree, naive bayes and random forest are trained and employed within the weka framework to label overlaps as either true or false. we show that by culling out the false overlaps and thus providing an overlap set that is closer to ideal, we are able to achieve longer contigs that cover a larger percentage of the genome. finally, yet perhaps most importantly, since large-scale sequencing and finished genomes are now ubiquitous, we show how we can leverage previous, related sequencing projects, if available, in the de novo assembly pipeline. while, other comparative assemblers, such as amoscmp map the reads to a single reference genome, we show how multiple reference genome sequences can be used to help assemble genomes. rather than produce a whole new genome assembler, we demonstrate our method by introducing it as a module into minimus, which is part of the modular open-source assembler project. although minimus is not as sophisticated as some other assemblers, amos is notable for being well-engineered and specifically designed to accept external modules and is thus an ideal test vehicle.  evaluation of reads from e. coli overlap statistics to determine if classification of overlaps can improve the assembly of sequencing reads, sequencing reads from salmonella enterica serovar typhi strain e were used to build training models within the weka framework, and reads from escherichia coli strain k substrain mg were used as a test set to assemble. the salmonella reads represented an approximately 8× coverage of the genome, while the e. coli reads represented an 18× coverage. reads from both strains were mapped to their respective genomes to determine the ground truth in regards to whether any predicted overlaps were true or false overlaps. because the completed genome for strain e was not available, the s. enterica serovar typhi ty genome, which shares approximately 96% identity with the e reads, was used instead. the amos hash-overlap program was used to identify potential overlaps. various statistics for these overlaps were calculated as described in the methods. these statistics included the percent mismatch within the overlap, the first, second, and third quartile k-mer frequencies, and a comparative genomics score. the quartile frequencies were derived by taking each k-mer within an overlap and calculating a normalized frequency of the k-mer within all reads. these frequencies were sorted from low to high, and the value of the frequency at each quartile of the distribution of frequencies was calculated. the distributions of these statistics as a function of the percentage of overlaps were calculated for these features within e. coli mg to show that in fact these features could partially discriminate true from false overlaps. as a percentage of total overlaps within the true or false categories, the false overlaps had a larger tail for the percent mismatch score. since there were a large number of true overlaps compared to false overlaps, the total number of true overlaps with having 1% to 2% mismatches was still higher than false overlaps. the k-mer distributions are shown in figure 1c-e. as expected, false overlaps tended to have a greater k-mer frequency. to see if reads from false overlaps tended to be in repetitive parts of the genome, blat, with a minimum score of was used to determine the number of times each read mapped to the reference genome. reads from true overlaps mapped on average times to the reference genome, while reads from false overlaps mapped on average to the reference genome. finally a comparative genomics score was generated by mapping the reads to a set of related e. coli genomes. a positive score was generated when the top match of each read mapped to the same location within a genome. a negative score was generated when the top match of each read was not in the same location within a genome. see methods for a detailed description of the comparative genomics score. classification accuracy as true and false overlaps had different distributions for the features that were tested, we next wanted to see if these features could be used to train classifiers that could be used to predict true and false overlaps. the accuracy of various machine learning algorithms in distinguishing true and false overlaps was explored. for the results shown in table both comparative and non-comparative features were used. salmonella reads were used to generate the training models used below, and e. coli reads were used as the test set. for the comparative score, genomes with less than 91% identity to salmonella ty or e. coli mg were used. accuracy was defined as the number of correctly predicted overlaps, divided by the total number of overlaps. the false positive rate was defined as the number of overlaps incorrectly predicted as positive, divided by the total number of actual false overlaps. the false negative rate was defined as the number of overlaps incorrectly predicted as false divided by the total number of actual true overlaps. the j classifier had the highest accuracy and the second lowest false positive rate. the naïve bayes classifier with default parameters produced the lowest false postive rate but had the highest false negative rate of the machine learning classifiers. using kernel estimation with naïve bayes improved the accuracy of the classifier and had the lowest false negative rate. confusion matrices for the classifiers are shown in additional file tables s and s one example decision tree for the j classifier using both comparative and non-comparative data is shown in additional file table s 1accuracy is defined as the number of true positive and true negative overlaps divided by the total number of overlaps 2the false positive rate is defined as the number of false positive overlaps divided by the number of false overlaps 3the false negative rate is defined as the number of false negative overlaps divided by the number of true overlaps 4naïvebayes with kernel estimation we wanted to compare the accuracy of our classifier with other methods of curating overlaps, which are typically rule-based. the latest version of the umd overlapper program uses a simple rule involving k-mer frequencies to label overlaps as reliable and unreliable. although this classification is not intended to be utilized for labeling overlaps as strictly true or false, it is similar in spirit, and we evaluated how well the reliable and unreliable categories aligned to true and false overlaps respectively. the overall accuracy of the reliability labeling was only %. the false positive rate was % and the false negative rate was %. assembly of e. coli sequencing reads the features from the s. typhi training set were used to generate several training models using classifiers such as j naïve bayes and random forest within the weka framework. overlaps from the e. coli reads were generated and classified using the training models. after removal of overlaps predicted to be false, the reads were assembled using minimus. the n score and the percentage of the reference genome matched by contigs were calculated for each assembly. the n score was defined as the maximum contig size where all contigs of that size and larger covered 50% of the genome. a higher n score generally represents the presence of larger contigs and thus a better assembly of the reads. as a control, we first assembled e. coli reads without classification and removal of overlaps predicted to be false. this assembly had an n score of and % of the reference genome was matched. while several classifiers were tested, including naïvebayes and random forest, the j classifier generally, but not always, produced better assembly results based on n scores and the percentage of the reference genome matched. we also attempted to use support vector machines within weka, but the classifier failed to finish due to the large number of overlaps involved. the results presented here represent the values from the j classification. the first set of training models were built using the non-comparative features such as mismatch percentage and the k-mer frequencies. the j model produced an n size and a percent genome matched of %. the next model to be analyzed was built using comparative features alone. for generating the comparative score within the test set, we excluded those strain that were highly similar to the test strain. by using this compartive score alone, the assembly produced contigs with an n score of and a percent match to the reference genome of %. assembling the reads using both the comparative and non-comparative features yielded an assembly with an n score of and a percent match to the reference genome of %. if we reduced the allowable strains for the comparative feature to those less than 91% identity, the n score and percent match for the comparative features alone dropped to and %. using both comparative and non-comparative features increased these values to and %, respectively. in addition to using the n statistic, we examined the n statistic for a range of n with several of the assemblies. again, the assembly using both comparative and non-comparative features provided the best results for most of the values of n between and additional file figure s shows the range of n statistics for assemblies using genomes <97% identical. for some genome sequencing projects, there may not be a large number of related genomes, as there are for e. coli and salmonella. therefore, the assembly was repeated using only two related genomes for the training and test set. for salmonella ty s. enterica serovar paratyphi strain atcc and s. enterica serovar typhimurium lt were used as related genomes. for the mg test assembly, e. coli strains atcc and e24377a were used as related genomes. for the j classifier the n score was and the percentage of the reference genome matched by the contigs was %. if only ty for salmonella and atcc for e. coli were used as related genomes, the n score for j decreased to and the percentage of the reference genome matched fell to. these results suggest that there does not need to be a large number of related genomes required for comparisons. see additional file figure s for a graph of these values. analysis of assembly quality dnadiff was used to identify gross mis-assemblies of the e. coli sequencing reads. we focused on the assembly using non-comparative features combined with the comparative feature using strains less than 97% identity. dnadiff reported two potential misjoins and a single tandem deletion for both the uncorrected and corrected assemblies. as a qualitative view of the assemblies, we used mauve to align assembled contigs that had been ordered by snapper to the finished reference genome. figure shows the alignment of the uncorrected. figure 4a shows the uncorrected assembly, while 3b shows the assembly after overlaps predicted to be false by the j classifier were removed. for both 3a and 3b, the assembled contigs are shown mapped to the reference sequence. contig boundaries are shown by vertical red bars. different colored blocks represent regions where contigs are in the correct order. breaks in the correct order of the contigs with respect to the reference genome are shown by the boundaries between colored block, and by the crossing colored lines. while there are several cases of contigs not being in the correct order, manual inspection of the breaks show that these occur in repetitive regions and do not represent true errors, only differences between alignment algorithms of snapper and mauve. we were not able to detect any gross mis-assemblies from the alignments. evaluation of sanger reads from s. aureus to determine if classification of overlaps could be applied to other types of data sets, we next analyzed sanger reads from staphylococcus aureus. reads from strain jh were used as a training set and reads from strain jh were used in the test set. both sets of reads represented an approximately 9× coverage of their respective genomes. the assembly of jh using uncorrected overlaps produced contigs with an n score of that matched % of the reference genome. using non-comparative features produced little improvement. with comparative feature using all s. aureus strains except jh and jh the assembly was improved, while including non-comparative features reduced the assembly quality slightly. however when only strains with less than 94% identity to jh and jh were used for the comparative score, the results of using both non-comparative and comparative features were better than comparative features alone. the a plot of the n statistic for range of n is shown in additional file figure s  by providing a more accurate approximation of the true overlap structure of the input reads, overlap classification can simplify the task of contig construction and thereby create superior assemblies. in particular, the addition of information from related genomes strengthens the quality of the assembly, without sacrificing the flexibility of the de novo framework for a purely comparative assembly process with a single reference genome such as provided by amoscmp. use of related genomes can potentially be generalized to other aspects of de novo assembly, including the de bruijn approach where this information can be used to resolve pairs of branches. from the results shown here, if highly similar genomes are available, a purely comparative approach will likely yield better results. however, if these sequences are not available, using a machine learning approach using non-comparative and comparative features from more distantly related reference genomes can improve sequence assembly. the overlap classification implementation described here was tested in a rather simple genome assembler, and may produce a smaller percentage improvement of the n length if placed in more sophisticated assemblers. on the other hand, the bacterial genomes utilized as test cases are not particularly repetitive; it is hypothesized that the results could be even stronger in repeat-rich genomes. in our experiments, the size of the training set did not have an impact on the results, allowing the use of smaller training sets than test sets. once trained, the decision tree can be quickly applied to new overlaps, and thus the computational time taken by the overlap correction module was in line with other modules in the assembly process. the alignment statistics should be computed during the overlap process to maximize efficiency and the reads must be searched for high-quality hits to reference genome, but neither of these presents an excessive computational burden compared to other phases of genome assembly. it should therefore be possible to apply overlap correction to larger genomes. 
we trained several different classification models within the weka framework using various statistics derived from overlaps of reads available from prior sequencing projects. we present an approach that extends the minimus assembler by a data driven step to classify overlaps as true or false prior to contig construction. these statistics included percent mismatch and k-mer frequencies within the overlaps as well as a comparative genomics score derived from mapping reads to multiple reference genomes. we show that in real whole-genome sequencing data from the e. coli and s. aureus genomes, by providing a curated set of overlaps to the contigging phase of the assembler, we nearly doubled the median contig length without sacrificing coverage of the genome or increasing the number of mis-assemblies. machine learning methods that use comparative and non-comparative features to classify overlaps as true or false can be used to improve the quality of a sequence assembly. but no overlapping algorithm to date takes a rigorous approach to separating aligned but non-overlapping read pairs from true overlaps.
 with the rapid expansion of dna sequencing databases, it is now feasible to identify relevant information from prior sequencing projects and completed genomes and apply it to de novo sequencing of new organisms. as an example, this paper demonstrates how such extra information can be used to improve de novo assemblies by augmenting the overlapping step. finding all pairs of overlapping reads is a key task in many genome assemblers, and to this end, highly efficient algorithms have been developed to find alignments in large collections of sequences. it is well known that due to repeated sequences, many aligned pairs of reads nevertheless do not overlap. but no overlapping algorithm to date takes a rigorous approach to separating aligned but non-overlapping read pairs from true overlaps.  we present an approach that extends the minimus assembler by a data driven step to classify overlaps as true or false prior to contig construction. we trained several different classification models within the weka framework using various statistics derived from overlaps of reads available from prior sequencing projects. these statistics included percent mismatch and k-mer frequencies within the overlaps as well as a comparative genomics score derived from mapping reads to multiple reference genomes. we show that in real whole-genome sequencing data from the e. coli and s. aureus genomes, by providing a curated set of overlaps to the contigging phase of the assembler, we nearly doubled the median contig length without sacrificing coverage of the genome or increasing the number of mis-assemblies.  machine learning methods that use comparative and non-comparative features to classify overlaps as true or false can be used to improve the quality of a sequence assembly. 