BACKGROUND
next-generation sequencing platforms such as illumina, abi solid, and  <dig> allow genomes to be sequenced more quickly and at a lower cost than ever before.
however, as sequencing technology has improved, the wealth of available data has not made genome assembly easier.
in fact, the level of difficulty has increased, as the cost savings provided by new technologies are accompanied by a reduction in achievable read-length.
assembly software is now faced with the task of assembling reads ranging from approximately  <dig> to  <dig> nucleotides, in contrast to the 800- <dig> nucleotide reads previously generated by the traditional sanger technology.
additionally, the error characteristics of the newer technologies are not as well known as they were for traditional sanger sequencing.
de novo assemblies  are highly fragmented  <cit> .
in addition, advances in sequencing technologies have not been mirrored by corresponding improvements in finishing - a time-, labor-, and cost-intensive process aimed at reconstructing a complete, gapless, genome sequence from a fragmented assembly.
as a result, the majority of genomes remain in an incomplete 'draft' state, hampering studies that rely on long-range genome structure information .
genomic repeats - dna segments repeated in nearly-identical form throughout a genome - are the main reason why genome assemblers cannot automatically reconstruct complete genome sequences from modern sequencing data.
repeats have a number of biological causes, including transposable sequence elements , prophages, highly-conserved gene clusters , or large segmental duplications, and can vary from short simple sequence repeats  to long stretches of dna  that are highly or completely identical.
in the context of inexpensive next-generation sequencing and assembly, some of the original pitfalls of genome assembly, such as coverage gaps and confusion caused by read errors, can often be obviated by simply sequencing the genome to very high coverage levels.
repeated sequences, on the other hand, cannot be avoided by simply over-sequencing, and lead to considerable ambiguity in the reconstruction of a genome, providing limits on the length of the contiguous dna segments  that can be correctly reconstructed using unpaired reads  <cit> .
graph-theoretic models of genome assembly provide an effective framework for analyzing the impact of repeats on the complexity of genome assembly  <cit> .
the genome assembly problem is commonly formulated as finding a constrained path through an appropriately-defined graph.
throughout this article we will rely on an eulerian formulation  <cit>  that reduces the assembly problem to finding a chinese postman path/tour  within a de bruijn graph .
under this formulation, repeats appear as forks in the graph that make it difficult to select the graph traversal that corresponds to the correct reconstruction of the genome from among an exponential  number of possible chinese post-man paths.
without additional information, genome assemblers can only correctly reconstruct relatively short, unordered segments of the genome .
in addition to the collection of reads, most sequencing technologies also produce pairwise constraints on the placement  of these reads along the genome - mate-pair information.
this information can further constrain the possible traversals of the assembly graph, thereby allowing longer segments of the genome to be unambiguously reconstructed.
mate-pair information has been a critical component of most genome projects, starting with haemophilus influenzae  <cit>  - the first free-living organism to be fully sequenced.
most genome assemblers now include modules that can use mate-pair information for scaffolding and repeat resolution , and stand-alone scaffolding tools such as bambus  <cit>  allow the incorporation of mate-pair data into virtually any assembly  <cit> .
furthermore, mate-pairs are frequently used for the purpose of assembly validation in tools such as baccardi  <cit> , consed  <cit> , and hawkeye  <cit> .
most of the research on the use of mate-pair information in genome projects has focused primarily on the use of this information to achieve long-range connectivity by spanning long repeats and gaps in the assembly due to insufficient sequencing coverage.
as a result, substantial efforts have been focused on the development of robust protocols for constructing long-range  mate-pair libraries.
here, we explore a complementary purpose for mate-pairs - the automatic resolution of repeats during assembly.
we argue that, due to affordable high-throughput sequencing technologies, coverage gaps are far less frequent than they used to be, and assembly fragmentation is primarily caused by repeats.
thus improvements in repeat resolution algorithms will translate into substantial improvements in the quality of the resulting assemblies.
resolving repeats with mate-pairs
all previously published techniques for repeat resolution rely on the same basic observation: if a unique path in the assembly graph can be found that connects the sequences at the ends of a mate-pair and the length of this path matches the approximately known mate-pair size, then this path can be inferred to be correct; i.e., the path represents a partial traversal of the graph that is consistent with the correct reconstruction of the genome being assembled.
since the problem of finding a path of predefined length through a graph is np-hard  <cit> , the algorithms used during assembly rely on various heuristics for efficiently finding paths that support mate-pair information.
the euler assembler  <cit>  greedily finds paths whose lengths are consistent with the size of mate-pairs , then converts these paths into artificial long reads that can be processed through the eulerian superpath algorithm  <cit> .
conflicts between paths through the graph are resolved by prioritizing paths on the basis of their support   <cit> .
the velvet  <cit>  and allpaths  <cit>  assemblers take into account the uniqueness of nodes in the assembly graph.
specifically, mate-pair links are considered only if they are anchored in contigs that correspond to non-repeated sequences in the genome .
analyses of the effectiveness of such algorithms have typically assumed the parameters of the sequencing experiment to be fixed; i.e., the goal is to build the best assembly possible given the types of data commonly generated in current sequencing projects.
an exception is the study by chaisson et al.
<cit>  where the authors evaluate the effect of read length and read quality on the ability to reconstruct a genome.
in other words, they assume one can tune the read length generated by a sequencing machine  and estimate whether the assembly improves, and by how much, if the length of reads is increased.
such analyses are critical for providing a scientific basis for picking the optimal trade-off between sequencing cost  and quality of assembly.
in our work, we pose a complementary question: how useful are mate-pairs for resolving repeats in de novo assemblies created from short-reads?
which types of mate-pair libraries most effectively resolve repeats and minimize the amount of manual finishing needed to complete the genome ?
similar questions have been addressed by recent publications in the context of sequence alignment.
chikhi et al.
<cit>  evaluate how read length affects genome resequencing experiments, and bashir et al.
<cit>  developed a method to identify the mate-pair sizes that are optimal for detecting structural variation through mapping.
however, the question of how effective mate-pairs are for the resolution of repeats and how this parameter of the sequencing experiment can be adjusted to improve assemblies has not previously been analyzed in a systematic fashion.
measuring assembler performance
metrics commonly used for comparing the quality of genome assemblies are primarily focused on statistics derived from the global distribution of contig sizes.
statistics such as the number of contigs, average contig size, and n <dig> contig size are frequently reported in the literature.
when the correct answer is known , one can also record the number of errors found in the assembly.
an alternative approach is proposed by chaisson et al.
<cit>  where they compare the results of an assembly to a theoretical optimal: the best assembly that can be reconstructed without errors from a genome, given the repeat graph  of that genome.
in our study we are specifically targeting this theoretical optimum: in an idealized setting , what is the best possible assembly that can be obtained given the parameters of the sequencing process?
while aiming for this theoretical optimum, we also maintain a dose of reality about certain aspects of sequencing projects, restricting ourselves to the use of only two mate-pair libraries  and use of read-lengths that are reflective of inexpensive next-generation sequencing.
like chaisson et al.
<cit>  and kingsford et al.
<cit> , we start with the idealized repeat graph of a genome , the structure of which is determined by the read length.
although we are attempting to maximize the size of contigs that can be unambiguously reconstructed from this graph, contig size statistics are difficult to compare across genomes and may not adequately describe the amount of repeat resolution that a set of mate-pairs provide.
therefore, we focus instead on a measure of assembly ambiguity that is directly related to unresolved repeats.
specifically, we measure the number of manual experiments that would be necessary to completely resolve the structure of a genome during finishing.
briefly, a path through the repeat graph can be uniquely determined by pairing up the edges adjacent to repeat nodes.
this pairing is commonly determined during finishing through targeted pcr experiments.
we measure the usefulness of a mate-pair library in terms of the amount of manual finishing effort that can be saved through its use .
we show that, in the context of high-depth prokaryotic sequencing experiments, very short mate-pairs are more useful than long mate-pairs  for resolving repeats, and that choosing mate-pair sizes based on the repeat structure  of the assembly graph is a powerful approach for creating more complete assemblies.
our results hold across  <dig> 'ideal' sequencing experiments  as well as when using an off-the-shelf assembler in the presence of base-call errors .
these results can serve as a basis for developing new algorithms and sequencing strategies that will improve de novo assemblies.
due to computational efficiency considerations we limited our analysis to prokaryotic genomes.
whether or not our results can be extended to eukaryotes  remains an exercise for future work.
RESULTS
we simulated ideal sequencing projects  for  <dig> complete bacterial genomes using a range of read lengths and mate-pair sizes.
read lengths were chosen to be reflective of reads that can be affordably obtained using next-generation sequencing platforms.
in addition, for  <dig> of these genomes, we performed a direct comparison of the amount of repeat resolution that can be obtained when applying information provided by long mate-pairs  vs. mate-pairs whose sizes are 'tuned' to the repeat structure of the genomes being assembled.
finally, we show that the results of our simulated comparison are recapitulated when assembling  <dig> bacterial genomes in the presence of base-call errors using an off -the-shelf assembler .
we assume a refined version of the repeat graph for a genome; specifically, the graph that can be obtained through a series of lossless transformations on the original de bruijn graph .
since all of the transformations used simply convert unambiguous paths from the original graph into single nodes, the resulting simplified structure is equivalent  to the original graph.
the simplified version of the graph is more compact and better highlights the complexity introduced by repeats, since every node in the simplified graph is either a repeat itself or is one of a set of possible nodes to traverse in between a pair of repeats.
throughout most of our analysis, we consider k-mer size  and read-length to be interchangeable, denoting both with the letter k. although read-length and k-mer size are not typically the same in a real sequencing and assembly experiment , we consider the distinction to be irrelevant throughout much of the discussion of our simulations; the only exception being the discussion of soapdenovo assemblies.
since our 'idealized' graphs  are constructed from complete genomes decomposed directly into k-mers, we implicitly imagine that we have perfect reads of length k and that they can be used in their entirety during graph construction.
since a read of length k can provide a k-mer of length at most k, ignoring the distinction still provides a valid  upper-bound on what one can expect to achieve if using reads of length k with a real assembler.
our results begin with some theoretical analysis of the usefulness and limitations of mate-pairs and then proceed to an empirical investigation into the benefits of 'tuning' mate-pair libraries to target repeats of high complexity.
it should be noted here that due to limitations of our current implementation to handle larger, eukaryotic de bruijn graphs, we have restricted the scope of our results to cover only assembly of prokaryotic genomes.
we intend to explore whether or not these results can be extended to eukaryotic assemblies in future work.
a complete set of data files produced for this experiment is available at: http://www.cbcb.umd.edu/~wetzeljo/matepairs/.
performance of shortest-path heuristic
our study relies on a simple heuristic for the use of mate-pair information: mate-pairs are only used if an unambiguous shortest path through the assembly graph connects its end-points and is consistent with the insert length.
medvedev et al.
<cit>  use a similar shortest-path approach in their maximum likelihood genome assembler.
while more elaborate approaches have been proposed , such methods are computationally expensive.
furthermore, we find that the length of a shortest path connecting the two ends of a mate-pair exactly matches the insert length almost 90% of the time, even for relatively long  libraries and short reads  .
for longer reads and shorter mate-pairs, this statistic approaches 100%.
the shortest-path heuristic is less effective only when using very long mate-pair inserts  with short reads .
in this case, as few as 62% of the mate-pairs correspond to a shortest path.
a table summarizing average  statistics across  <dig> prokaryotic genomes  when applying  <dig>  mate-pairs of a particular length to a graph constructed from k-mers of a particular length.
apercentage of mate-pairs that can be mapped to a shortest path in the graph when comparing exact length of the insert to length of the path.
bpercentage of mate-pairs that can ultimately provide unambiguous information for repeat resolution .
cpercent reduction in finishing effort  that the set of mate-pairs can provide.
while a large fraction of mate-pairs could, in principle, be used during assembly through the shortest-path heuristic, the vast majority of mate-pairs do not span repeat nodes, and many cannot yield unambiguous paths .
thus, most mate-pairs are not useful for repeat resolution.
for example, on average only  <dig> % of all mate-pairs from a  <dig> bp library could be used to resolve repeats  in assemblies constructed from  <dig> bp reads .
this result is unsurprising when the mate-pair length is short with respect to the read-length, as both ends of the mate-pair are usually found within the same node of the assembly graph.
however, even in the case when mate-pairs are significantly longer than the read length, only a small fraction of the mate-pairs are ultimately usable .
an intuitive explanation for this phenomenon is the observation that the genomic repeats that cause most of the complexity in a genome represent just a small fraction of the size of the genome.
only mate-pairs that span these, relatively rare, complexity hot-spots are useful during assembly.
while table  <dig> highlights the mate-pair statistics discussed here, table  <dig> provides a comprehensive set of statistics for all read/mate-pair-length combinations studied.
in the table below, a library of  <dig>  mate-pairs of a particular length was applied to each of the graphs for each of the  <dig> genomes listed in additional file  <dig>  the values refer to average percentages.
the first four columns refer the percentages retained by successive filtration steps used to identify and remove unusable mate-pairs: a% which had a shortest path of the prescribed length between end sequences, b% which crossed forks, c% which shortest path matched insert sequence, and d% which had a unique shortest path.
the final two percentage values  refer to overall percentages across all  <dig>  mate-pairs for each category.
as a corollary to the above observation, the value of mate-pairs is maximized only once sufficient coverage is achieved to ensure that virtually all resolvable repeats are adequately spanned.
the necessary number of mate-pairs is a function of the genome size g and the k-mer length k used for graph construction .
'localized complexity' is common in short-read assembly graphs
a surprising result of our study has been the fact that, for the majority of the genomes studied, assembly ambiguity can only be decreased up to a certain point irrespective of depth of coverage and library size, i.e.
mate-pair information appears to have limited value in resolving repeats.
closer inspection of the assembly graphs reveals a common motif that limits the applicability of mate-pair information.
specifically, we find pairs of repeat nodes , separated by two or more non-decision nodes of equal lengths.
frequently, chains of such patterns  can be found in many genomes.
assembly bubbles are difficult to resolve with mate-pairs because multiple equal-length paths can be found between the endpoints of mate-pairs that span the bubble structure.
thus mate-pairs which span bubbles provide no information on the order in which the intermediate non-decision nodes  need to be visited.
an example is shown in figure  <dig>  these regions of 'localized complexity' can only be resolved by mate-pairs that tightly span exactly one of the two repeats.
as we will show later, this phenomenon is common in bacterial genomes and highlights the need to tune mate-pair libraries to the specific repeat structure of each genome.
in order to estimate the extent of genomic complexity introduced by the bubble pattern described above, we define a measure of the localized complexity of a genome as follows.
for each repeat node, v ∈ g, we define the node to be 'trivial' if all of its successor nodes have distinct lengths, and 'non-trivial' otherwise.
the motivation for this nomenclature is that if v has multiple successors of the same length, it is likely that v fits the description of repeat r <dig> in the above stated example of an assembly bubble, and will be difficult to resolve without targeting at least one mate-pair to barely span its length.
on the other hand, if all successors of v are of different lengths, v cannot fit the description of r <dig> in the above example, and the proper traversal order of v can likely be resolved using mate-pairs of arbitrary  length.
thus we define the localized complexity of a genome, c-statistic, to be the percentage of the finishing complexity of the genome contained in non-trivial nodes  =  <dig> , where n is the set of non-trivial nodes in the assembly graph, s is the set of all nodes in the assembly graph, and cv is the contribution of node v to the finishing complexity of the genome .
as seen in figure  <dig>  roughly 60% of the  <dig>   <dig>  and 100-mer graphs have a c-statistic ranging between  <dig> and  <dig>  in other words, in about 60% of the graphs created from short reads, 60-90% of their total finishing complexity is contained within repeats that are difficult to resolve using mate-pair information.
the amount of localized complexity appears to be significantly lower for graphs created from longer reads: for 250-mer graphs, the average c-statistic was  <dig> %, and for the 500-mer graphs the average c-statistic was  <dig> %.
this implies that longer reads may be critical if the goal of assembly is to reconstruct entire genomes in an automated fashion.
the existence of bubbles in assembly graphs has been noted before, and several approaches have been suggested for resolving such regions .
our results imply that any such methods will be of limited use unless the mate-pair libraries are tuned to match the repeat structure of the genome being assembled.
'ideal' mate-pairs are short
we further explored the hypothesis that 'tuning' mate-pair libraries to accommodate a genome's specific repeat structure could lead to higher quality assemblies.
all repeats in a genome were grouped according to size into bins of width 4k, where k is the read length.
for each bin we calculated the fraction of the total finishing complexity  of the genome that is due to the repeats from that bin.
we then selected the two bins with the highest finishing complexities, and constructed mate-pair libraries that just span repeats in these bins by using inserts that were 3k longer than the average repeat size for each bin.
we restrict our analysis to just two libraries for any given genome to match the setting commonly encountered in practice.
mate-pairs selected in this fashion end up being roughly proportional in size to the read length, k, averaging from  <dig> k to 6k.
this is significantly shorter than commonly constructed long-range libraries .
as expected, the tuned insert length is greater for graphs with less localized complexity  than it is for graphs with greater amounts of localized complexity .
for  <dig>   <dig> and 100-mer graphs with a c-statistic of at least  <dig>  the mean ideal insert size was consistently short , while genomes with a lower c-statistic resulted in longer and more varied library sizes .
increased variation in ideal mate-pair size for graphs with lower c-statistic can likely be attributed to there being fewer graphs in this category .
these results are similar in spirit to, and complement, the euler-pcr algorithm proposed by mulyukov et al.
<cit> .
in euler-pcr, the assembler uses information about the repeat length  in order to minimize the number of primers and multiplex pcr experiments needed to resolve tangles in the graph.
essentially, the assembler is leveraging the repeat structure of the graph to find optimal sets of short mate-pairs to reduce manual finishing.
in the context of producing mate-pair libraries via sequencing, we cannot target individual repeats, so we instead attempt to find the mate-pair sizes that are most likely to resolve a large fraction of a genome's repeats.
'tuned' mate-pair libraries perform well in a simulated setting
to evaluate the effectiveness of the 'tuned' mate-pair libraries just described, we analyzed through simulations  <dig> bacterial genomes  across  <dig> different read lengths.
for each genome we compared the performance of the 'tuned' mate-pair libraries to a mixture of  <dig>  and  <dig>  bp libraries.
the latter mixture deserves a brief explanation: the majority of genome projects  rely on a mixture of library sizes, one of which is relatively long .
as we cannot feasibly test all possible combinations of library sizes, we chose a combination that is reasonable and roughly matches the 'typical' scenario used in sanger sequencing projects.
in both cases  the depth of coverage was the same, and was chosen to ensure that all repeats can be adequately spanned .
for each genome we recorded the finishing complexity  before and after the incorporation of mate-pair information, as well as the localized complexity  of the genome.
the tuned libraries, which generally consisted of very short mate-pairs , vastly outperformed the long-range libraries on graphs constructed from short reads .
the average reduction in finishing complexity was  <dig> % when using tuned libraries, in contrast to only  <dig> % when using a combination of long-range libraries .
for a combination of two long mate-pair libraries, one can see a clear inverse relationship between reduction in finishing complexity and c-statistic .
however, this relationship is greatly diminished for the tuned libraries .
this result is consistent with the observation that tuned library sizes are longer for the low complexity genomes, where chains of trivial repeats can often be resolved simultaneously by a single mate-pair.
while the results of simulations on 250-mer graphs were very similar to the results of simulations on the shorter-read graphs , the performance improvement over our 'standard' library mixture decreases for 500-mer graphs .
this can be attributed to the fact that the standard insert size of  <dig> bp is short  with respect to the original read length for the 500-mer graphs, while it is long  with respect to the original read length of the 250-mer graphs.
this result indicates that the need for tuning mate-pair lengths to the genome structure may be unique to the use of very short reads.
'tuned' mate-pair libraries improve performance when using off-the-shelf assembly software
in order to analyze the effectiveness of 'tuned' vs. long mate-pair libraries in a more realistic context, we created 30× coverage of  <dig> complete bacterial genomes  with  <dig> bp reads using metasim .
we then reassembled each genome given its set of reads and different combinations of long or tuned mate-pair libraries using soapdenovo v.  <dig>  .
for each genome, one pair of tuned libraries was based on the 'ideal' lengths predicted by our 35-mer graphs  and another pair was based on the ideal lengths predicted by our 100-mer graphs .
see table  <dig> for ideal mate-pair lengths for each genome.
'tuned' mate-pair lengths used when performing soapdenovo assemblies.
the values t <dig> and t <dig> refer to the best and second best mate-pair lengths respectively.
these values are based on determination of 'ideal' mate-pair sizes for the  <dig> and 100-mer graphs .
we found that in all but two of the cases, the pair of tuned libraries predicted by our 35-mer graphs were most effective at improving assemblies in terms of increasing average and maximum contig size, producing fewer total contigs, and increasing n <dig> contig size .
these libraries consisted of one library of length at most  <dig> bp and a second of less than  <dig> bp in all cases.
for the two cases in which the tuned libraries did not perform best, a single  <dig> bp library performed best.
however, when splitting read-coverage between libraries of size  <dig> and  <dig> bp, performance always suffered in comparison to the  <dig> bp library alone.
these findings highlight our previously stated result that shorter mate-pairs are generally more helpful in assembly of prokaryotes than are longer mate-pairs.
interestingly, the tuned libraries predicted by our 100-mer graphs typically perform quite poorly despite the fact that the assembly is built from  <dig> bp reads.
this indicates that despite the 'read-threading' procedure used by soapdenovo, information initially contained in a read is being lost when it is broken into shorter k-mers .
there is little to no overlap between soapdenovo's assembly algorithms and the methods we have described for applying mate-pairs to ideal graphs in our simulations; yet tuned libraries perform better in both situations, indicating that they are capturing a fundamental property of the genome structure.
contig statistics for various assemblies using soapdenovo with 'tuned' and 'standard' mate-pair libraries.
the standard sizes used were always  <dig> bp inserts or a combination of  <dig> bp and  <dig> bp inserts.
tuned sizes varied according to the prediction of ideal mate-pair sizes provided by analysis of our 35-mer and 100-mer graphs .
all assemblies used 30× coverage with  <dig> bp reads created by metasim.
the best assembly  for each organism is bold-faced.
discussion
there are a few difficulties we encounter when attempting to apply the exact quantitative analysis we describe above  to real assembly graphs.
first, while our ideal graphs are unambiguously directed, real assembly graphs are inherently bi-directed since dna is double-stranded.
therefore, it is not possible to directly transform graphs created from real data into unambiguously directed graphs so that the exact finishing complexity  can be computed.
specifically, our quantitative analysis requires that we know the in-degree and out-degree of a particular node, yet the direction in which the edges are traversed in a real graph is often not known until the assembly process.
additionally, since edge multiplicities in real sequencing experiments must be estimated based on various metrics such as depth of coverage and errors occur during sequencing, real assembly graphs are often disconnected and certainly not fully eulerian, further limiting the exact analysis described.
nonetheless, the strategy for choosing the 'tuned' mate-pair sizes should be applicable to real genome projects.
note that our strategy for tuning the library sizes requires information about the amount of genomic complexity implied by a particular set of repeats of similar size, i.e.
it is not sufficient to simply estimate the number and size of repeats from a genome assembly.
instead, the assembly graph  needs to be analyzed in more detail.
as we already mentioned, real assembly graphs have a different structure than the graphs used in our simulation.
in order to accommodate the non-eulerian nature of real assembly graphs, the methods we proposed can be converted to a chinese postman traversal setting, i.e., find a minimum-length tour of a non-eulerian graph that covers each edge at least once.
an efficient algorithm for solving this problem on bi-directed de bruijn graphs has been recently published  <cit> .
the resulting chinese postman tour implies an underlying eulerian graph  within which the algorithms described in our work can be applied.
specifically, within this implied graph we can compute, for each repeat, the corresponding finishing complexity which, together with the repeat size , can be used as outlined in the results  to heuristically determine appropriate mate-pair sizes.
in future work we plan to build a software package that performs this analysis for commonly used genome assemblers.
CONCLUSIONS
our results demonstrate that dramatic improvements in the quality of prokaryotic genome assemblies can be achieved by tuning mate-pair sizes to the actual repeat structure of a genome, suggesting the possible need to change the way that such sequencing projects are designed.
in many sequencing projects, library sizes are chosen based on the ease with which certain size libraries can be effectively constructed in the lab.
virtually always, the mate-pair libraries are constructed at the beginning of the project, before having an opportunity to evaluate the repeat structure of the genome being sequenced.
this 'one-step' approach was unavoidable in the case of sanger sequencing where mate-pairs were a by-product of the sequencing process .
in the case of next-generation sequencing technologies, however, the protocols were originally developed for creating unpaired reads, and the generation of mate-pairs generally increases the costs  of sequencing.
in this context, the two-tiered approach we propose - first generate an assembly of the genome with unpaired reads and evaluate the repeat structure of the genome; then generate the mate-pair libraries that provide most information towards the resolution of repeats in the genome being assembled - is not only possible, but likely more cost-effective in the long run.
the tuned mate-pair libraries produced by this process will be more usable by the assembler, leading to better assemblies , which will dramatically reduce the cost of downstream manual finishing.
across all of the genomes examined, as read lengths get shorter, the overall efficacy of mate-pairs in reducing finishing complexity is almost always diminished regardless of the amount of localized complexity present in the genome.
this result is supported by the empirical observation that genome assemblies constructed from short-read data  are typically substantially more fragmented than those constructed with longer reads   <cit> , further underscoring the need to develop affordable sequencing technologies that generate long reads.
many advances have been made in the field of automatic genome assembly in the past several years.
here we have shown that a novel, two-tiered approach to sequencing projects  can greatly improve automation.
however, even under ideal circumstances , we still found ourselves unable to produce completely gapless assemblies in many cases.
on average, approximately 17% of the original finishing complexity of a given genome still remained after applying mate-pairs.
thus, although the automation process continues to improve, the development of high-throughput and cost-effective approaches for genome finishing will also be of great importance in the years to come.

 next-generation sequencing platforms such as illumina, abi solid, and allow genomes to be sequenced more quickly and at a lower cost than ever before. however, as sequencing technology has improved, the wealth of available data has not made genome assembly easier. in fact, the level of difficulty has increased, as the cost savings provided by new technologies are accompanied by a reduction in achievable read-length. assembly software is now faced with the task of assembling reads ranging from approximately to nucleotides, in contrast to the 800- nucleotide reads previously generated by the traditional sanger technology. additionally, the error characteristics of the newer technologies are not as well known as they were for traditional sanger sequencing. de novo assemblies are highly fragmented. in addition, advances in sequencing technologies have not been mirrored by corresponding improvements in finishing - a time-, labor-, and cost-intensive process aimed at reconstructing a complete, gapless, genome sequence from a fragmented assembly. as a result, the majority of genomes remain in an incomplete'draft' state, hampering studies that rely on long-range genome structure information. genomic repeats - dna segments repeated in nearly-identical form throughout a genome - are the main reason why genome assemblers cannot automatically reconstruct complete genome sequences from modern sequencing data. repeats have a number of biological causes, including transposable sequence elements, prophages, highly-conserved gene clusters, or large segmental duplications, and can vary from short simple sequence repeats to long stretches of dna that are highly or completely identical. in the context of inexpensive next-generation sequencing and assembly, some of the original pitfalls of genome assembly, such as coverage gaps and confusion caused by read errors, can often be obviated by simply sequencing the genome to very high coverage levels. repeated sequences, on the other hand, cannot be avoided by simply over-sequencing, and lead to considerable ambiguity in the reconstruction of a genome, providing limits on the length of the contiguous dna segments that can be correctly reconstructed using unpaired reads. graph-theoretic models of genome assembly provide an effective framework for analyzing the impact of repeats on the complexity of genome assembly. the genome assembly problem is commonly formulated as finding a constrained path through an appropriately-defined graph. throughout this article we will rely on an eulerian formulation that reduces the assembly problem to finding a chinese postman path/tour within a de bruijn graph. under this formulation, repeats appear as forks in the graph that make it difficult to select the graph traversal that corresponds to the correct reconstruction of the genome from among an exponential number of possible chinese post-man paths. without additional information, genome assemblers can only correctly reconstruct relatively short, unordered segments of the genome. in addition to the collection of reads, most sequencing technologies also produce pairwise constraints on the placement of these reads along the genome - mate-pair information. this information can further constrain the possible traversals of the assembly graph, thereby allowing longer segments of the genome to be unambiguously reconstructed. mate-pair information has been a critical component of most genome projects, starting with haemophilus influenzae - the first free-living organism to be fully sequenced. most genome assemblers now include modules that can use mate-pair information for scaffolding and repeat resolution, and stand-alone scaffolding tools such as bambus allow the incorporation of mate-pair data into virtually any assembly. furthermore, mate-pairs are frequently used for the purpose of assembly validation in tools such as baccardi, consed, and hawkeye. most of the research on the use of mate-pair information in genome projects has focused primarily on the use of this information to achieve long-range connectivity by spanning long repeats and gaps in the assembly due to insufficient sequencing coverage. as a result, substantial efforts have been focused on the development of robust protocols for constructing long-range mate-pair libraries. here, we explore a complementary purpose for mate-pairs - the automatic resolution of repeats during assembly. we argue that, due to affordable high-throughput sequencing technologies, coverage gaps are far less frequent than they used to be, and assembly fragmentation is primarily caused by repeats. thus improvements in repeat resolution algorithms will translate into substantial improvements in the quality of the resulting assemblies. resolving repeats with mate-pairs all previously published techniques for repeat resolution rely on the same basic observation: if a unique path in the assembly graph can be found that connects the sequences at the ends of a mate-pair and the length of this path matches the approximately known mate-pair size, then this path can be inferred to be correct; i.e., the path represents a partial traversal of the graph that is consistent with the correct reconstruction of the genome being assembled. since the problem of finding a path of predefined length through a graph is np-hard, the algorithms used during assembly rely on various heuristics for efficiently finding paths that support mate-pair information. the euler assembler greedily finds paths whose lengths are consistent with the size of mate-pairs, then converts these paths into artificial long reads that can be processed through the eulerian superpath algorithm. conflicts between paths through the graph are resolved by prioritizing paths on the basis of their support. the velvet and allpaths assemblers take into account the uniqueness of nodes in the assembly graph. specifically, mate-pair links are considered only if they are anchored in contigs that correspond to non-repeated sequences in the genome. analyses of the effectiveness of such algorithms have typically assumed the parameters of the sequencing experiment to be fixed; i.e., the goal is to build the best assembly possible given the types of data commonly generated in current sequencing projects. an exception is the study by chaisson et al. where the authors evaluate the effect of read length and read quality on the ability to reconstruct a genome. in other words, they assume one can tune the read length generated by a sequencing machine and estimate whether the assembly improves, and by how much, if the length of reads is increased. such analyses are critical for providing a scientific basis for picking the optimal trade-off between sequencing cost and quality of assembly. in our work, we pose a complementary question: how useful are mate-pairs for resolving repeats in de novo assemblies created from short-reads? which types of mate-pair libraries most effectively resolve repeats and minimize the amount of manual finishing needed to complete the genome? similar questions have been addressed by recent publications in the context of sequence alignment. chikhi et al. evaluate how read length affects genome resequencing experiments, and bashir et al. developed a method to identify the mate-pair sizes that are optimal for detecting structural variation through mapping. however, the question of how effective mate-pairs are for the resolution of repeats and how this parameter of the sequencing experiment can be adjusted to improve assemblies has not previously been analyzed in a systematic fashion. measuring assembler performance metrics commonly used for comparing the quality of genome assemblies are primarily focused on statistics derived from the global distribution of contig sizes. statistics such as the number of contigs, average contig size, and n contig size are frequently reported in the literature. when the correct answer is known, one can also record the number of errors found in the assembly. an alternative approach is proposed by chaisson et al. where they compare the results of an assembly to a theoretical optimal: the best assembly that can be reconstructed without errors from a genome, given the repeat graph of that genome. in our study we are specifically targeting this theoretical optimum: in an idealized setting, what is the best possible assembly that can be obtained given the parameters of the sequencing process? while aiming for this theoretical optimum, we also maintain a dose of reality about certain aspects of sequencing projects, restricting ourselves to the use of only two mate-pair libraries and use of read-lengths that are reflective of inexpensive next-generation sequencing. like chaisson et al. and kingsford et al., we start with the idealized repeat graph of a genome, the structure of which is determined by the read length. although we are attempting to maximize the size of contigs that can be unambiguously reconstructed from this graph, contig size statistics are difficult to compare across genomes and may not adequately describe the amount of repeat resolution that a set of mate-pairs provide. therefore, we focus instead on a measure of assembly ambiguity that is directly related to unresolved repeats. specifically, we measure the number of manual experiments that would be necessary to completely resolve the structure of a genome during finishing. briefly, a path through the repeat graph can be uniquely determined by pairing up the edges adjacent to repeat nodes. this pairing is commonly determined during finishing through targeted pcr experiments. we measure the usefulness of a mate-pair library in terms of the amount of manual finishing effort that can be saved through its use. we show that, in the context of high-depth prokaryotic sequencing experiments, very short mate-pairs are more useful than long mate-pairs for resolving repeats, and that choosing mate-pair sizes based on the repeat structure of the assembly graph is a powerful approach for creating more complete assemblies. our results hold across'ideal' sequencing experiments as well as when using an off-the-shelf assembler in the presence of base-call errors. these results can serve as a basis for developing new algorithms and sequencing strategies that will improve de novo assemblies. due to computational efficiency considerations we limited our analysis to prokaryotic genomes. whether or not our results can be extended to eukaryotes remains an exercise for future work.  we simulated ideal sequencing projects for complete bacterial genomes using a range of read lengths and mate-pair sizes. read lengths were chosen to be reflective of reads that can be affordably obtained using next-generation sequencing platforms. in addition, for of these genomes, we performed a direct comparison of the amount of repeat resolution that can be obtained when applying information provided by long mate-pairs vs. mate-pairs whose sizes are'tuned' to the repeat structure of the genomes being assembled. finally, we show that the results of our simulated comparison are recapitulated when assembling bacterial genomes in the presence of base-call errors using an off -the-shelf assembler. we assume a refined version of the repeat graph for a genome; specifically, the graph that can be obtained through a series of lossless transformations on the original de bruijn graph. since all of the transformations used simply convert unambiguous paths from the original graph into single nodes, the resulting simplified structure is equivalent to the original graph. the simplified version of the graph is more compact and better highlights the complexity introduced by repeats, since every node in the simplified graph is either a repeat itself or is one of a set of possible nodes to traverse in between a pair of repeats. throughout most of our analysis, we consider k-mer size and read-length to be interchangeable, denoting both with the letter k. although read-length and k-mer size are not typically the same in a real sequencing and assembly experiment, we consider the distinction to be irrelevant throughout much of the discussion of our simulations; the only exception being the discussion of soapdenovo assemblies. since our'idealized' graphs are constructed from complete genomes decomposed directly into k-mers, we implicitly imagine that we have perfect reads of length k and that they can be used in their entirety during graph construction. since a read of length k can provide a k-mer of length at most k, ignoring the distinction still provides a valid upper-bound on what one can expect to achieve if using reads of length k with a real assembler. our results begin with some theoretical analysis of the usefulness and limitations of mate-pairs and then proceed to an empirical investigation into the benefits of'tuning' mate-pair libraries to target repeats of high complexity. it should be noted here that due to limitations of our current implementation to handle larger, eukaryotic de bruijn graphs, we have restricted the scope of our results to cover only assembly of prokaryotic genomes. we intend to explore whether or not these results can be extended to eukaryotic assemblies in future work. a complete set of data files produced for this experiment is available at: http://www.cbcb.umd.edu/~wetzeljo/matepairs/. performance of shortest-path heuristic our study relies on a simple heuristic for the use of mate-pair information: mate-pairs are only used if an unambiguous shortest path through the assembly graph connects its end-points and is consistent with the insert length. medvedev et al. use a similar shortest-path approach in their maximum likelihood genome assembler. while more elaborate approaches have been proposed, such methods are computationally expensive. furthermore, we find that the length of a shortest path connecting the two ends of a mate-pair exactly matches the insert length almost 90% of the time, even for relatively long libraries and short reads. for longer reads and shorter mate-pairs, this statistic approaches 100%. the shortest-path heuristic is less effective only when using very long mate-pair inserts with short reads. in this case, as few as 62% of the mate-pairs correspond to a shortest path. a table summarizing average statistics across prokaryotic genomes when applying mate-pairs of a particular length to a graph constructed from k-mers of a particular length. apercentage of mate-pairs that can be mapped to a shortest path in the graph when comparing exact length of the insert to length of the path. bpercentage of mate-pairs that can ultimately provide unambiguous information for repeat resolution. cpercent reduction in finishing effort that the set of mate-pairs can provide. while a large fraction of mate-pairs could, in principle, be used during assembly through the shortest-path heuristic, the vast majority of mate-pairs do not span repeat nodes, and many cannot yield unambiguous paths. thus, most mate-pairs are not useful for repeat resolution. for example, on average only % of all mate-pairs from a bp library could be used to resolve repeats in assemblies constructed from bp reads. this result is unsurprising when the mate-pair length is short with respect to the read-length, as both ends of the mate-pair are usually found within the same node of the assembly graph. however, even in the case when mate-pairs are significantly longer than the read length, only a small fraction of the mate-pairs are ultimately usable. an intuitive explanation for this phenomenon is the observation that the genomic repeats that cause most of the complexity in a genome represent just a small fraction of the size of the genome. only mate-pairs that span these, relatively rare, complexity hot-spots are useful during assembly. while table highlights the mate-pair statistics discussed here, table provides a comprehensive set of statistics for all read/mate-pair-length combinations studied. in the table below, a library of mate-pairs of a particular length was applied to each of the graphs for each of the genomes listed in additional file the values refer to average percentages. the first four columns refer the percentages retained by successive filtration steps used to identify and remove unusable mate-pairs: a% which had a shortest path of the prescribed length between end sequences, b% which crossed forks, c% which shortest path matched insert sequence, and d% which had a unique shortest path. the final two percentage values refer to overall percentages across all mate-pairs for each category. as a corollary to the above observation, the value of mate-pairs is maximized only once sufficient coverage is achieved to ensure that virtually all resolvable repeats are adequately spanned. the necessary number of mate-pairs is a function of the genome size g and the k-mer length k used for graph construction.'localized complexity' is common in short-read assembly graphs a surprising result of our study has been the fact that, for the majority of the genomes studied, assembly ambiguity can only be decreased up to a certain point irrespective of depth of coverage and library size, i.e. mate-pair information appears to have limited value in resolving repeats. closer inspection of the assembly graphs reveals a common motif that limits the applicability of mate-pair information. specifically, we find pairs of repeat nodes, separated by two or more non-decision nodes of equal lengths. frequently, chains of such patterns can be found in many genomes. assembly bubbles are difficult to resolve with mate-pairs because multiple equal-length paths can be found between the endpoints of mate-pairs that span the bubble structure. thus mate-pairs which span bubbles provide no information on the order in which the intermediate non-decision nodes need to be visited. an example is shown in figure these regions of'localized complexity' can only be resolved by mate-pairs that tightly span exactly one of the two repeats. as we will show later, this phenomenon is common in bacterial genomes and highlights the need to tune mate-pair libraries to the specific repeat structure of each genome. in order to estimate the extent of genomic complexity introduced by the bubble pattern described above, we define a measure of the localized complexity of a genome as follows. for each repeat node, v ∈ g, we define the node to be'trivial' if all of its successor nodes have distinct lengths, and'non-trivial' otherwise. the motivation for this nomenclature is that if v has multiple successors of the same length, it is likely that v fits the description of repeat r in the above stated example of an assembly bubble, and will be difficult to resolve without targeting at least one mate-pair to barely span its length. on the other hand, if all successors of v are of different lengths, v cannot fit the description of r in the above example, and the proper traversal order of v can likely be resolved using mate-pairs of arbitrary length. thus we define the localized complexity of a genome, c-statistic, to be the percentage of the finishing complexity of the genome contained in non-trivial nodes =, where n is the set of non-trivial nodes in the assembly graph, s is the set of all nodes in the assembly graph, and cv is the contribution of node v to the finishing complexity of the genome. as seen in figure roughly 60% of the and 100-mer graphs have a c-statistic ranging between and in other words, in about 60% of the graphs created from short reads, 60-90% of their total finishing complexity is contained within repeats that are difficult to resolve using mate-pair information. the amount of localized complexity appears to be significantly lower for graphs created from longer reads: for 250-mer graphs, the average c-statistic was %, and for the 500-mer graphs the average c-statistic was %. this implies that longer reads may be critical if the goal of assembly is to reconstruct entire genomes in an automated fashion. the existence of bubbles in assembly graphs has been noted before, and several approaches have been suggested for resolving such regions. our results imply that any such methods will be of limited use unless the mate-pair libraries are tuned to match the repeat structure of the genome being assembled.'ideal' mate-pairs are short we further explored the hypothesis that'tuning' mate-pair libraries to accommodate a genome's specific repeat structure could lead to higher quality assemblies. all repeats in a genome were grouped according to size into bins of width 4k, where k is the read length. for each bin we calculated the fraction of the total finishing complexity of the genome that is due to the repeats from that bin. we then selected the two bins with the highest finishing complexities, and constructed mate-pair libraries that just span repeats in these bins by using inserts that were 3k longer than the average repeat size for each bin. we restrict our analysis to just two libraries for any given genome to match the setting commonly encountered in practice. mate-pairs selected in this fashion end up being roughly proportional in size to the read length, k, averaging from k to 6k. this is significantly shorter than commonly constructed long-range libraries. as expected, the tuned insert length is greater for graphs with less localized complexity than it is for graphs with greater amounts of localized complexity. for and 100-mer graphs with a c-statistic of at least the mean ideal insert size was consistently short, while genomes with a lower c-statistic resulted in longer and more varied library sizes. increased variation in ideal mate-pair size for graphs with lower c-statistic can likely be attributed to there being fewer graphs in this category. these results are similar in spirit to, and complement, the euler-pcr algorithm proposed by mulyukov et al.. in euler-pcr, the assembler uses information about the repeat length in order to minimize the number of primers and multiplex pcr experiments needed to resolve tangles in the graph. essentially, the assembler is leveraging the repeat structure of the graph to find optimal sets of short mate-pairs to reduce manual finishing. in the context of producing mate-pair libraries via sequencing, we cannot target individual repeats, so we instead attempt to find the mate-pair sizes that are most likely to resolve a large fraction of a genome's repeats.'tuned' mate-pair libraries perform well in a simulated setting to evaluate the effectiveness of the'tuned' mate-pair libraries just described, we analyzed through simulations bacterial genomes across different read lengths. for each genome we compared the performance of the'tuned' mate-pair libraries to a mixture of and bp libraries. the latter mixture deserves a brief explanation: the majority of genome projects rely on a mixture of library sizes, one of which is relatively long. as we cannot feasibly test all possible combinations of library sizes, we chose a combination that is reasonable and roughly matches the'typical' scenario used in sanger sequencing projects. in both cases the depth of coverage was the same, and was chosen to ensure that all repeats can be adequately spanned. for each genome we recorded the finishing complexity before and after the incorporation of mate-pair information, as well as the localized complexity of the genome. the tuned libraries, which generally consisted of very short mate-pairs, vastly outperformed the long-range libraries on graphs constructed from short reads. the average reduction in finishing complexity was % when using tuned libraries, in contrast to only % when using a combination of long-range libraries. for a combination of two long mate-pair libraries, one can see a clear inverse relationship between reduction in finishing complexity and c-statistic. however, this relationship is greatly diminished for the tuned libraries. this result is consistent with the observation that tuned library sizes are longer for the low complexity genomes, where chains of trivial repeats can often be resolved simultaneously by a single mate-pair. while the results of simulations on 250-mer graphs were very similar to the results of simulations on the shorter-read graphs, the performance improvement over our'standard' library mixture decreases for 500-mer graphs. this can be attributed to the fact that the standard insert size of bp is short with respect to the original read length for the 500-mer graphs, while it is long with respect to the original read length of the 250-mer graphs. this result indicates that the need for tuning mate-pair lengths to the genome structure may be unique to the use of very short reads.'tuned' mate-pair libraries improve performance when using off-the-shelf assembly software in order to analyze the effectiveness of'tuned' vs. long mate-pair libraries in a more realistic context, we created 30× coverage of complete bacterial genomes with bp reads using metasim. we then reassembled each genome given its set of reads and different combinations of long or tuned mate-pair libraries using soapdenovo v.. for each genome, one pair of tuned libraries was based on the'ideal' lengths predicted by our 35-mer graphs and another pair was based on the ideal lengths predicted by our 100-mer graphs. see table for ideal mate-pair lengths for each genome.'tuned' mate-pair lengths used when performing soapdenovo assemblies. the values t and t refer to the best and second best mate-pair lengths respectively. these values are based on determination of'ideal' mate-pair sizes for the and 100-mer graphs. we found that in all but two of the cases, the pair of tuned libraries predicted by our 35-mer graphs were most effective at improving assemblies in terms of increasing average and maximum contig size, producing fewer total contigs, and increasing n contig size. these libraries consisted of one library of length at most bp and a second of less than bp in all cases. for the two cases in which the tuned libraries did not perform best, a single bp library performed best. however, when splitting read-coverage between libraries of size and bp, performance always suffered in comparison to the bp library alone. these findings highlight our previously stated result that shorter mate-pairs are generally more helpful in assembly of prokaryotes than are longer mate-pairs. interestingly, the tuned libraries predicted by our 100-mer graphs typically perform quite poorly despite the fact that the assembly is built from bp reads. this indicates that despite the'read-threading' procedure used by soapdenovo, information initially contained in a read is being lost when it is broken into shorter k-mers. there is little to no overlap between soapdenovo's assembly algorithms and the methods we have described for applying mate-pairs to ideal graphs in our simulations; yet tuned libraries perform better in both situations, indicating that they are capturing a fundamental property of the genome structure. contig statistics for various assemblies using soapdenovo with'tuned' and'standard' mate-pair libraries. the standard sizes used were always bp inserts or a combination of bp and bp inserts. tuned sizes varied according to the prediction of ideal mate-pair sizes provided by analysis of our 35-mer and 100-mer graphs. all assemblies used 30× coverage with bp reads created by metasim. the best assembly for each organism is bold-faced. discussion there are a few difficulties we encounter when attempting to apply the exact quantitative analysis we describe above to real assembly graphs. first, while our ideal graphs are unambiguously directed, real assembly graphs are inherently bi-directed since dna is double-stranded. therefore, it is not possible to directly transform graphs created from real data into unambiguously directed graphs so that the exact finishing complexity can be computed. specifically, our quantitative analysis requires that we know the in-degree and out-degree of a particular node, yet the direction in which the edges are traversed in a real graph is often not known until the assembly process. additionally, since edge multiplicities in real sequencing experiments must be estimated based on various metrics such as depth of coverage and errors occur during sequencing, real assembly graphs are often disconnected and certainly not fully eulerian, further limiting the exact analysis described. nonetheless, the strategy for choosing the'tuned' mate-pair sizes should be applicable to real genome projects. note that our strategy for tuning the library sizes requires information about the amount of genomic complexity implied by a particular set of repeats of similar size, i.e. it is not sufficient to simply estimate the number and size of repeats from a genome assembly. instead, the assembly graph needs to be analyzed in more detail. as we already mentioned, real assembly graphs have a different structure than the graphs used in our simulation. in order to accommodate the non-eulerian nature of real assembly graphs, the methods we proposed can be converted to a chinese postman traversal setting, i.e., find a minimum-length tour of a non-eulerian graph that covers each edge at least once. an efficient algorithm for solving this problem on bi-directed de bruijn graphs has been recently published. the resulting chinese postman tour implies an underlying eulerian graph within which the algorithms described in our work can be applied. specifically, within this implied graph we can compute, for each repeat, the corresponding finishing complexity which, together with the repeat size, can be used as outlined in the results to heuristically determine appropriate mate-pair sizes. in future work we plan to build a software package that performs this analysis for commonly used genome assemblers.  our results demonstrate that dramatic improvements in the quality of prokaryotic genome assemblies can be achieved by tuning mate-pair sizes to the actual repeat structure of a genome, suggesting the possible need to change the way that such sequencing projects are designed. in many sequencing projects, library sizes are chosen based on the ease with which certain size libraries can be effectively constructed in the lab. virtually always, the mate-pair libraries are constructed at the beginning of the project, before having an opportunity to evaluate the repeat structure of the genome being sequenced. this'one-step' approach was unavoidable in the case of sanger sequencing where mate-pairs were a by-product of the sequencing process. in the case of next-generation sequencing technologies, however, the protocols were originally developed for creating unpaired reads, and the generation of mate-pairs generally increases the costs of sequencing. in this context, the two-tiered approach we propose - first generate an assembly of the genome with unpaired reads and evaluate the repeat structure of the genome; then generate the mate-pair libraries that provide most information towards the resolution of repeats in the genome being assembled - is not only possible, but likely more cost-effective in the long run. the tuned mate-pair libraries produced by this process will be more usable by the assembler, leading to better assemblies, which will dramatically reduce the cost of downstream manual finishing. across all of the genomes examined, as read lengths get shorter, the overall efficacy of mate-pairs in reducing finishing complexity is almost always diminished regardless of the amount of localized complexity present in the genome. this result is supported by the empirical observation that genome assemblies constructed from short-read data are typically substantially more fragmented than those constructed with longer reads, further underscoring the need to develop affordable sequencing technologies that generate long reads. many advances have been made in the field of automatic genome assembly in the past several years. here we have shown that a novel, two-tiered approach to sequencing projects can greatly improve automation. however, even under ideal circumstances, we still found ourselves unable to produce completely gapless assemblies in many cases. on average, approximately 17% of the original finishing complexity of a given genome still remained after applying mate-pairs. thus, although the automation process continues to improve, the development of high-throughput and cost-effective approaches for genome finishing will also be of great importance in the years to come. 
we show that, in high-coverage prokaryotic assemblies, libraries of short mate-pairs more effectively disambiguate repeat regions than the libraries that are commonly constructed in current genome projects. in future work we intend to address the question of whether this result can be extended to larger eukaryotic genomes, where repeat structure can be quite different. our results demonstrate that dramatic improvements in prokaryotic genome assembly quality can be achieved by tuning mate-pair sizes to the actual repeat structure of a genome, suggesting the possible need to change the way sequencing projects are designed. the assembly results show that our method of tuning mate-pairs exploits fundamental properties of these genomes, leading to better assemblies even when using an off -the-shelf assembler in the presence of base-call errors. these results are shown across simulations on'ideal' prokaryotic data as well as assembly of bacterial genomes using soapdenovo. the simulation results provide an upper-bound on the potential value of mate-pairs for resolving repeated sequences in real prokaryotic data sets. here, we examine the effectiveness of mate-pair information in resolving repeated sequences in the dna. however, as sequencing technology has improved, the difficulty of de novo genome assembly has increased, due in large part to the shorter reads generated by the new technologies. we also demonstrate that the best assemblies can be obtained by'tuning' mate-pair libraries to accommodate the specific repeat structure of the genome being assembled - information that can be obtained through an initial assembly using unpaired reads. while it has been empirically accepted that mate-pairs improve assemblies, and a variety of assemblers use mate-pairs in the context of repeat resolution, the effectiveness of mate-pairs in this context has not been systematically evaluated in previous literature. we propose that a two-tiered approach - first generate an assembly of the genome with unpaired reads in order to evaluate the repeat structure of the genome; then generate the mate-pair libraries that provide most information towards the resolution of repeats in the genome being assembled - is not only possible, but likely also more cost-effective as it will significantly reduce downstream manual finishing costs.
 next-generation sequencing technologies allow genomes to be sequenced more quickly and less expensively than ever before. however, as sequencing technology has improved, the difficulty of de novo genome assembly has increased, due in large part to the shorter reads generated by the new technologies. the use of mated sequences is a standard means of disambiguating assemblies to obtain a more complete picture of the genome without resorting to manual finishing. here, we examine the effectiveness of mate-pair information in resolving repeated sequences in the dna. while it has been empirically accepted that mate-pairs improve assemblies, and a variety of assemblers use mate-pairs in the context of repeat resolution, the effectiveness of mate-pairs in this context has not been systematically evaluated in previous literature.  we show that, in high-coverage prokaryotic assemblies, libraries of short mate-pairs more effectively disambiguate repeat regions than the libraries that are commonly constructed in current genome projects. we also demonstrate that the best assemblies can be obtained by'tuning' mate-pair libraries to accommodate the specific repeat structure of the genome being assembled - information that can be obtained through an initial assembly using unpaired reads. these results are shown across simulations on'ideal' prokaryotic data as well as assembly of bacterial genomes using soapdenovo. the simulation results provide an upper-bound on the potential value of mate-pairs for resolving repeated sequences in real prokaryotic data sets. the assembly results show that our method of tuning mate-pairs exploits fundamental properties of these genomes, leading to better assemblies even when using an off -the-shelf assembler in the presence of base-call errors.  our results demonstrate that dramatic improvements in prokaryotic genome assembly quality can be achieved by tuning mate-pair sizes to the actual repeat structure of a genome, suggesting the possible need to change the way sequencing projects are designed. we propose that a two-tiered approach - first generate an assembly of the genome with unpaired reads in order to evaluate the repeat structure of the genome; then generate the mate-pair libraries that provide most information towards the resolution of repeats in the genome being assembled - is not only possible, but likely also more cost-effective as it will significantly reduce downstream manual finishing costs. in future work we intend to address the question of whether this result can be extended to larger eukaryotic genomes, where repeat structure can be quite different. 