BACKGROUND
today, next-generation sequencing  technologies are essential tools in genome analysis, because they enable us to simultaneously obtain sequences of up to hundreds of billions of base pairs  <cit> .
these technologies enable the characterization of not only small variations such as single-nucleotide polymorphisms  but also large-scale mutations such as insertions, deletions, tandem duplications, and inversions.
mutations of these types are collectively called structural variations  and are frequently observed even in healthy individuals  <cit> .
because svs affect a much larger portion of genomes than small variations, including snps, they have a great impact on biological functions.
current ngs methods can sequence paired reads, which are pairs of reads several hundred bases away from each other.
this ability is useful for analyzing svs because paired reads can be aligned with the reference genome more accurately than single reads, and because we can analyze structures of genomes larger than the size of each read.
however, sv detection is still a difficult task, because it requires analysis of the complex structures involved in an enormous number of alignments of paired reads with the reference genome, and because read sequences and alignments include unavoidable errors.
therefore, for example, a false detection rate  up to 10% had to be tolerated even when determining just the existence of each sv in the  <dig> genomes project  <cit> .
it is obviously more difficult to accurately detect the exact positions of svs.
nevertheless, high-resolution sv calls are necessary to elucidate the functional impact of svs and molecular mechanisms that generate svs.
moreover, to conduct a large-scale analysis, sv detection methods for data with a low depth of coverage  are desirable, because whole genome sequencing is not easy even with ngs technologies.
current methods for sv detection search for signatures that indicate svs hidden in read sequences and their alignments with the genome sequences.
the following are basic signatures used for sv detection  <cit> .
• read pair   <cit> : if pairs of reads have aberrant strands or distances, they are likely to be caused by svs.
such pairs are called discordant pairs, and normally mapped ones are called concordant pairs.
if strands of a discordant pair are as expected, a larger distance than expected indicates a deletion, whereas a smaller distance indicates an insertion.
there are several categories of methods that detect discordant pairs by using mapping distances.
• threshold-based: a pair with a mapped distance larger or smaller than a predefined threshold is defined as a discordant pair.
the threshold is μ± <dig> σor μ± <dig> σfor breakdancer  <cit>  and variationhunter  <cit>  where μand σare mean and standard deviation of mapping distances, or median fragment size ±  <dig> median absolute deviations for hydra  <cit> .
• distribution-based: although the mapped distance of a single pair might vary by tens or hundreds bases even without svs, larger  mapping distances of many pairs in the same region indicate deletions .
such reads can be detected by statistical tests on the distribution of mapped distances  <cit> .
pairs detected in this way might have mapping distances more similar to the expected distance than those of other methods.
nonetheless, we still call them discordant pairs in this paper to unify the word used to refer pairs that support svs.
• graph-based: recently marshall et al.
<cit>  proposed a new method clever based on the graph theory.
clever constructs a graph where a node represents an alignment of a read pair and the genome, while an edge means that connected alignments potentially support the same allele.
in this graph, a clique corresponds to a set of pairs supporting the same allele.
clever detects svs by finding maximal cliques .
clever has an ability to find more than one max-clique overlaping each other, each of which supports a different allele.
therefore clever can distinguish more than one sv located at the same locus, for example, two deletions of different sizes in a diploid genome.
• read depth   <cit> : if coverage changes at some position in the genome, this indicates a copy number variation.
• split read   <cit> : if an alignment of a read and the genome includes only a part of the read, this indicates a position of a breakpoint.
here, a breakpoint is the boundary between a region affected by some sv and its unaffected flanking region.
• sequence assembly   <cit> : if the coverage is sufficient, assembling ngs reads around an sv reveals the exact sequence around the sv and the positions of breakpoints.
the most popular signature used to detect svs is threshold-based rp.
methods based on this signature can detect svs from a small number of discordant read pairs; therefore threshold-based rp methods can be applied to low-coverage data.
however, threshold-based rp methods localize svs only to regions surrounded by discordant read pairs, thus causing some ambiguity.
for rd methods, the problem of resolution is much bigger.
because rd methods involve calculation of coverage in windows of a fixed size, its resolution cannot be finer than the window size.
methods based on the sr signature can determine positions of breakpoints up to base-pair-level  resolution if there are reads covering the breakpoints.
however, such reads might not exist, in particular when coverage is low, because of unevenness of coverage or repeat elements to which reads cannot be aligned uniquely.
moreover, because such a split alignment is shorter than a read itself, careful analysis is required to avoid spurious matches.
if coverage is sufficiently high, as methods would ultimately reveal the exact positions of svs at bp-level resolution.
although extremely deep sequencing can be conducted by targeted sequencing  <cit> , it is still expensive to obtain paired reads of high coverage over the entire genome so that assembly can be performed.
in fact, a previous study has indicated that the sensitivity of as methods is rather low .
because these signatures have their own advantages and disadvantages, it is desirable to combine more than one method  <cit> .
in fact, several methods that use more than one signature have been proposed recently  <cit> .
in combined approaches, we should integrate sv signatures that are independent of each other.
in this paper, we propose a new method called chopsticks that improves the resolution of deletion calls for homozygous deletions generated mainly by threshold-based rp methods.
chopsticks is especially valuable when target svs are expected to be homozygous as those of inbred mice whose genomes are homozygous at virtually all loci  <cit> .
chopsticks exploits positions of concordant read pairs in addition to those of discordant ones.
thus far, they have been ignored in threshold-based rp approaches, and therefore, our method can improve the resolution by using this new independent information.
as explained below, chopsticks is effective even for data whose coverage is low.
the organization of this paper is as follows.
first, we theoretically analyze the improvement of the resolution achieved by exploiting concordant read pairs.
next, we present our computational method chopsticks that improves the resolution of homozygous deletion calls.
after that, we demonstrate the effectiveness of chopsticks in computational experiments.
then, we present our conclusions.
in addition, we illustrate details of our method and experiments in methods section.
RESULTS
strategy for resolution improvement
theoretical estimation of resolution
here we present results of our theoretical analysis of improved resolution achieved by our method as compared to rp methods.
we also present the necessary definitions to describe them.
see methods for details.
we define a discordant read as a read of a discordant pair and a concordant read as that of a concordant pair.
among the two reads of a pair, the one mapped upstream is called an upstream read and the other is called a downstream read in this paper.
let c be the depth of coverage.
assume that the positions of read pairs are uniformly random over the genome, and that the length r of each read is a fixed constant.
let q be the probability that there is no read pair whose upstream read begins at a given base in the genome.
suppose that there are n read pairs uniquely mapped to a genomic sequence of length g. according to a classical analysis  <cit> ,
q=1−1gn≈e−n/g=e−c/2r.
hereafter, we just write q instead of q for simplicity.
in threshold-based rp approaches, the predicted position of an upstream end of a deletion is determined by the upstream discordant read that is the closest to the breakpoint.
let b be the position of an upstream end of a deletion, Δb be the distance between b and the closest upstream discordant read, and d be the distance between paired reads.
we assume that d is a constant.
let e be the expectation of Δbgiven that b is detected and the coverage is c. then,
e=1−q1−qd+1s,
where
s=∑j=0djqj=q−qd+1+dqd+ <dig>
see methods for derivation of equation .
we can obtain better resolution by using concordant reads in addition to discordant reads, because there is a chance that there exists a concordant read closer to b than any upstream discordant read .
such a read can contribute to the localization of the position where b can exist.
let Δb′ be the distance between b and the closest read in the upstream of b, and let e be the expectation of Δb′ given that b is detected and the coverage is c. then,
e=11−qd+1×s−qd+1s.
as shown in figure  <dig>  the expected resolution of our method is significantly superior to that of threshold-based rp methods, which only use discordant pairs.
the achieved resolution is quite close to that of threshold-based rp methods but with double coverage, which we confirmed theoretically.
theorem 1
the expectation e is a weighted sum of e and e. to be more precise, the following equation holds:
e=e−qd+1e.
see methods for the proof.
when c→ <dig>  both e and e approach d/ <dig>  which is the expected resolution when a deletion is detected with only one read pair.
therefore e also approaches d/ <dig> when c→ <dig>  on the other hand, when c approaches infinity, e approaches e because qd + 1→ <dig>  in summary,
theorem 2
e is asymptotically equal to e when c→ <dig> or c→∞.
trimming of deletion calls to improve resolution
if all regions existing in the reference genome were covered by at least one read and there were absolutely no reads mapped to regions of homozygous deletions, the resolution of deletion calls could be quite easily improved by just trimming the ends of deletion calls that are covered by alignments of reads.
obviously, such a simple assumption does not hold in practical situations.
first, coverage might be zero even in regions that actually exist in the genome, because no reads are obtained therein owing to the unevenness of the coverage or because reads cannot be uniquely mapped owing to repeat elements.
second, there might exist erroneous alignments in deleted regions because of incidental sequence similarity.
therefore, we developed the algorithm chopsticks to carefully trim the ends of deletion calls .
chopsticks recognizes high-coverage regions close to the ends of deletion calls even if they are fragmented, and it repeatedly excludes the high-coverage regions from deletion calls.
chopsticks uses two parameters, k and f. the k parameter is a threshold used to distinguish high-coverage regions from low-coverage ones, and f determines the threshold of joint coverage of regions excluded from a deletion call.
see methods for details.
our implementation of chopsticks is available on the internet  <cit> .
.
computational experiment
to evaluate the power of chopsticks in improving the resolution of deletion calls, we conducted computational experiments.
let the upstream difference of a deletion call be x−y, where x is the position of the upstream end of the true deletion and y be that of the deletion call.
similarly, let the downstream difference of a deletion call be y′−x′, where x′ is the position of the downstream end of the true deletion and y′is that of the deletion call.
by definition, the closer to zero a difference is, the better.
a positive difference value indicates that the called breakpoint is outside the true deletion, whereas a negative value indicates that it is inside the true deletion.
to evaluate chopsticks, the results of chopsticks have to be compared with the positions of true deletions.
therefore we need ngs reads of a genome whose svs against the reference genome are known up to bp-level resolution.
we conducted two experiments described below.
simulated reads
in the first experiment, we evaluated chopsticks with simulated ngs reads for which all svs were known up to bp-level resolution.
to obtain data as realistic as possible, we generated a genome sequence with svs and simulated ngs sequences by using sv annotations published by quinlan et al.
<cit> .
the accession number of the sv annotations is .
first, we deleted regions of the reference genome sequence that were annotated as deletions by quinlan et al.
next, we inserted random fragments whose number and distribution of lengths were the same as annotated deletions, assuming that deletions and insertions are symmetric.
then, we introduced single nucleotide substitutions into the simulated genome sequence and generated paired reads from it.
we conducted this simulation and evaluation of chopsticks for chromosome  <dig> of the reference mouse genome mm <dig>  all paired reads were mapped to mm <dig> using burrows-wheeler aligner   <cit> .
then we conducted sv analysis by using sv detection tools from each of categories described in the background section: breakdancer  <cit>  of threshold-based rp methods, modil  <cit>  of distribution-based rp methods, clever  <cit>  of graph-based rp methods, cnvnator  <cit>  of rd methods, and pindel  <cit>  of sr methods.
after that, we applied chopsticks to their results.
before applying chopsticks, we examined the ability of sv detection tools to detect  <dig> deletions in chromosome  <dig> of the simulated mouse genome.
we say that a deletion call is correct if it overlaps exactly one true deletion while the true deletion in turn overlaps exactly one deletion call.
we show the number of called and correct sv calls in table  <dig>  we also show their recall  and precision  in figure  <dig>  the recall of breakdancer and clever was relatively good for all of tried coverage values, whereas the recall of pindel was satisfactory only when coverage was high.
the recall of modil was low for all coverage values tried.
although almost all deletions called by these methods were correct, cnvnator generated numerous false positives .
because chopsticks is developed to correct breakpoints outside true deletions, we counted the number of deletion calls that cover the whole of true deletions.
as shown in figure  <dig>  most of the deletion calls by modil, cnvnator, and pindel covered the whole of true deletions.
however, a significant portion of breakdancer and clever results did not cover the whole of true deletions.
note that chopsticks is harmless to these deletion calls because chopsticks does not trim them when there are no alignments in true deletions.
results of deletion calls by breakdancer, modil, clever, cnvnator, and pindel.
the values to the left of ”/” are the numbers of correct deletion calls, where a correct deletion call is the one that overlaps with exactly one true deletion, which, in turn, only overlaps with the deletion call; the values to the right of ”/” are the numbers of all deletion calls.
breakdancer and clever results were good in both sensitivity and specificity.
cnvnator generated numerous false positives, while pindel suffered from low coverage.
modil missed lots of deletions.
next, we applied chopsticks to the results of sv detection tools.
after that, we examined how well the resolution of deletion calls was improved.
we tested chopsticks for k= <dig> ,…, <dig> and f= <dig> , <dig> ,…, <dig> .
we evaluated differences at both the upstream and downstream ends of deletions, and found that the results were similar.
therefore we only present the results at upstream ends.
resolution improvements for breakdancer deletion calls
as shown in figure  <dig>  the resolution of deletion calls was clearly improved by using chopsticks.
the original breakdancer results was successfully corrected, which is also clear in figure  <dig>  when coverage was low, the resolution was well improved for small k values.
when coverage was high, the resolution was also improved for large k values.
therefore, when the coverage is high, we recommend using large k values to ignore erroneous alignments.
as shown in figure  <dig>  chopsticks worked well regardless of deletion lengths.
resolution improvements for modil deletion calls
as shown in figure  <dig>  the resolution of deletion calls by modil was also improved by using chopsticks.
we omitted evaluation of modil for coverage= <dig> because modil was very slow .
resolution improvements for clever deletion calls
the resolution of deletion calls by clever was also improved by using chopsticks.
as mentioned above, deletion calls of clever do not always cover the whole of true deletions.
nonetheless, as shown in figure  <dig> and  <dig>  chopsticks successfully improved resolution of clever results by selectively correcting predicted breakpoints outside true deletions.
resolution improvements for cnvnator deletion calls
because rd methods call svs by examining coverages in windows of a fixed size, the positions of breakpoints predicted by the rd methods have unavoidable ambiguity and they might be either inside or outside true deletions.
because chopsticks assumes that predicted breakpoints are outside true deletions, we applied chopsticks after we expanded deletion calls of cnvnator at both ends by the window size.
as shown in figure  <dig>  the results of cnvnator were successfully improved.
this result indicates that chopsticks is also available for rd methods in addition to rp methods.
results of chopsticks applied to pindel deletion calls
owing to the sr signature that allows pindel to detect svs at bp-level resolution, the positions of breakpoints obtained with pindel were quite accurate.
when chopsticks was applied to the results of pindel, the results became slightly worse than the original pindel results, as shown in figure  <dig>  although differences remained close to zero in most cases.
note that the recall of pindel was not satisfactory when coverage is low, as shown in figure  <dig>  chopsticks is useful in cases where deletions missed by pindel are analyzed.
real illumina reads of dba/2j
in the second experiment, we evaluated chopsticks using the real ngs sequences of quinlan et al.
<cit> .
the sample was taken from a female mouse of the dba/2j strain, whose genome contains svs against the reference genome of the c57bl/6j strain  <cit> .
the read sequences were available from the ncbi sequence read archive  database  <cit> .
the accession number of the read sequences is .
to evaluate the results of chopsticks, we need bp-level sv annotations of dba/2j as well.
therefore we generated deletion calls at bp-level resolution using sanger reads in a manner similar to that of quinlan et al.
see methods for details.
our deletion calls are available at the dbvar database under accession no.
.
we tried the five sv detection tools used in the previous experiment, and found that modil, cnvnator and pindel missed the most of deletions detected with sanger reads.
these methods seemed to suffer from the low depth of coverage and short read lengths.
therefore, we hereafter only describe results of chopsticks applied to breakdancer and clever results.
resolution improvements for breakdancer deletion calls
resolution improvements for clever deletion calls
clever detected much more  deletions than breakdancer.
the results of clever were also improved by chopsticks as shown in figure  <dig>  where the peak around zero became stronger.
however, it was difficult for chopsticks to correct positions of breakpoints when they were away from those predicted with sanger reads by hundreds of bases.
CONCLUSIONS
we have presented a new method called chopsticks to improve the resolution of predicted positions of deletions.
the key idea is to exploit both concordant read pairs and discordant ones.
according to our theoretical analysis, the resolution of our method is quite similar to that of threshold-based rp methods but with double coverage.
in an experiment on simulated ngs reads, chopsticks clearly improved the results of breakdancer, modil, clever, and cnvnator.
although the resolution of pindel results is quite high, chopsticks works well even for low-coverage data where recall of pindel is not sufficient.
the effectiveness of chopsticks was also confirmed by performing an experiment on real illumina reads.
despite a number of methods proposed for detecting svs  <cit> , there is no one-stop method that simultaneously achieves high sensitivity, high specificity, high resolution, and robustness for low-coverage data.
therefore a combination of sv detection methods is required, and chopsticks can play an important role because it uses new independent information ignored in other methods.
as a future work, we consider to develop a method to distinguish homozygous deletions from heterozygous ones and to apply chopsticks to the former.
with this approach, chopsticks will be available for more applications.

 today, next-generation sequencing technologies are essential tools in genome analysis, because they enable us to simultaneously obtain sequences of up to hundreds of billions of base pairs. these technologies enable the characterization of not only small variations such as single-nucleotide polymorphisms but also large-scale mutations such as insertions, deletions, tandem duplications, and inversions. mutations of these types are collectively called structural variations and are frequently observed even in healthy individuals. because svs affect a much larger portion of genomes than small variations, including snps, they have a great impact on biological functions. current ngs methods can sequence paired reads, which are pairs of reads several hundred bases away from each other. this ability is useful for analyzing svs because paired reads can be aligned with the reference genome more accurately than single reads, and because we can analyze structures of genomes larger than the size of each read. however, sv detection is still a difficult task, because it requires analysis of the complex structures involved in an enormous number of alignments of paired reads with the reference genome, and because read sequences and alignments include unavoidable errors. therefore, for example, a false detection rate up to 10% had to be tolerated even when determining just the existence of each sv in the genomes project. it is obviously more difficult to accurately detect the exact positions of svs. nevertheless, high-resolution sv calls are necessary to elucidate the functional impact of svs and molecular mechanisms that generate svs. moreover, to conduct a large-scale analysis, sv detection methods for data with a low depth of coverage are desirable, because whole genome sequencing is not easy even with ngs technologies. current methods for sv detection search for signatures that indicate svs hidden in read sequences and their alignments with the genome sequences. the following are basic signatures used for sv detection. • read pair: if pairs of reads have aberrant strands or distances, they are likely to be caused by svs. such pairs are called discordant pairs, and normally mapped ones are called concordant pairs. if strands of a discordant pair are as expected, a larger distance than expected indicates a deletion, whereas a smaller distance indicates an insertion. there are several categories of methods that detect discordant pairs by using mapping distances. • threshold-based: a pair with a mapped distance larger or smaller than a predefined threshold is defined as a discordant pair. the threshold is μ± σor μ± σfor breakdancer and variationhunter where μand σare mean and standard deviation of mapping distances, or median fragment size ± median absolute deviations for hydra. • distribution-based: although the mapped distance of a single pair might vary by tens or hundreds bases even without svs, larger mapping distances of many pairs in the same region indicate deletions. such reads can be detected by statistical tests on the distribution of mapped distances. pairs detected in this way might have mapping distances more similar to the expected distance than those of other methods. nonetheless, we still call them discordant pairs in this paper to unify the word used to refer pairs that support svs. • graph-based: recently marshall et al. proposed a new method clever based on the graph theory. clever constructs a graph where a node represents an alignment of a read pair and the genome, while an edge means that connected alignments potentially support the same allele. in this graph, a clique corresponds to a set of pairs supporting the same allele. clever detects svs by finding maximal cliques. clever has an ability to find more than one max-clique overlaping each other, each of which supports a different allele. therefore clever can distinguish more than one sv located at the same locus, for example, two deletions of different sizes in a diploid genome. • read depth: if coverage changes at some position in the genome, this indicates a copy number variation. • split read: if an alignment of a read and the genome includes only a part of the read, this indicates a position of a breakpoint. here, a breakpoint is the boundary between a region affected by some sv and its unaffected flanking region. • sequence assembly: if the coverage is sufficient, assembling ngs reads around an sv reveals the exact sequence around the sv and the positions of breakpoints. the most popular signature used to detect svs is threshold-based rp. methods based on this signature can detect svs from a small number of discordant read pairs; therefore threshold-based rp methods can be applied to low-coverage data. however, threshold-based rp methods localize svs only to regions surrounded by discordant read pairs, thus causing some ambiguity. for rd methods, the problem of resolution is much bigger. because rd methods involve calculation of coverage in windows of a fixed size, its resolution cannot be finer than the window size. methods based on the sr signature can determine positions of breakpoints up to base-pair-level resolution if there are reads covering the breakpoints. however, such reads might not exist, in particular when coverage is low, because of unevenness of coverage or repeat elements to which reads cannot be aligned uniquely. moreover, because such a split alignment is shorter than a read itself, careful analysis is required to avoid spurious matches. if coverage is sufficiently high, as methods would ultimately reveal the exact positions of svs at bp-level resolution. although extremely deep sequencing can be conducted by targeted sequencing, it is still expensive to obtain paired reads of high coverage over the entire genome so that assembly can be performed. in fact, a previous study has indicated that the sensitivity of as methods is rather low. because these signatures have their own advantages and disadvantages, it is desirable to combine more than one method. in fact, several methods that use more than one signature have been proposed recently. in combined approaches, we should integrate sv signatures that are independent of each other. in this paper, we propose a new method called chopsticks that improves the resolution of deletion calls for homozygous deletions generated mainly by threshold-based rp methods. chopsticks is especially valuable when target svs are expected to be homozygous as those of inbred mice whose genomes are homozygous at virtually all loci. chopsticks exploits positions of concordant read pairs in addition to those of discordant ones. thus far, they have been ignored in threshold-based rp approaches, and therefore, our method can improve the resolution by using this new independent information. as explained below, chopsticks is effective even for data whose coverage is low. the organization of this paper is as follows. first, we theoretically analyze the improvement of the resolution achieved by exploiting concordant read pairs. next, we present our computational method chopsticks that improves the resolution of homozygous deletion calls. after that, we demonstrate the effectiveness of chopsticks in computational experiments. then, we present our conclusions. in addition, we illustrate details of our method and experiments in methods section.  strategy for resolution improvement theoretical estimation of resolution here we present results of our theoretical analysis of improved resolution achieved by our method as compared to rp methods. we also present the necessary definitions to describe them. see methods for details. we define a discordant read as a read of a discordant pair and a concordant read as that of a concordant pair. among the two reads of a pair, the one mapped upstream is called an upstream read and the other is called a downstream read in this paper. let c be the depth of coverage. assume that the positions of read pairs are uniformly random over the genome, and that the length r of each read is a fixed constant. let q be the probability that there is no read pair whose upstream read begins at a given base in the genome. suppose that there are n read pairs uniquely mapped to a genomic sequence of length g. according to a classical analysis, q=1−1gn≈e−n/g=e−c/2r. hereafter, we just write q instead of q for simplicity. in threshold-based rp approaches, the predicted position of an upstream end of a deletion is determined by the upstream discordant read that is the closest to the breakpoint. let b be the position of an upstream end of a deletion, Δb be the distance between b and the closest upstream discordant read, and d be the distance between paired reads. we assume that d is a constant. let e be the expectation of Δbgiven that b is detected and the coverage is c. then, e=1−q1−qd+1s, where s=∑j=0djqj=q−qd+1+dqd+ see methods for derivation of equation. we can obtain better resolution by using concordant reads in addition to discordant reads, because there is a chance that there exists a concordant read closer to b than any upstream discordant read. such a read can contribute to the localization of the position where b can exist. let Δb′ be the distance between b and the closest read in the upstream of b, and let e be the expectation of Δb′ given that b is detected and the coverage is c. then, e=11−qd+1×s−qd+1s. as shown in figure the expected resolution of our method is significantly superior to that of threshold-based rp methods, which only use discordant pairs. the achieved resolution is quite close to that of threshold-based rp methods but with double coverage, which we confirmed theoretically. theorem 1 the expectation e is a weighted sum of e and e. to be more precise, the following equation holds: e=e−qd+1e. see methods for the proof. when c→ both e and e approach d/ which is the expected resolution when a deletion is detected with only one read pair. therefore e also approaches d/ when c→ on the other hand, when c approaches infinity, e approaches e because qd + 1→ in summary, theorem 2 e is asymptotically equal to e when c→ or c→∞. trimming of deletion calls to improve resolution if all regions existing in the reference genome were covered by at least one read and there were absolutely no reads mapped to regions of homozygous deletions, the resolution of deletion calls could be quite easily improved by just trimming the ends of deletion calls that are covered by alignments of reads. obviously, such a simple assumption does not hold in practical situations. first, coverage might be zero even in regions that actually exist in the genome, because no reads are obtained therein owing to the unevenness of the coverage or because reads cannot be uniquely mapped owing to repeat elements. second, there might exist erroneous alignments in deleted regions because of incidental sequence similarity. therefore, we developed the algorithm chopsticks to carefully trim the ends of deletion calls. chopsticks recognizes high-coverage regions close to the ends of deletion calls even if they are fragmented, and it repeatedly excludes the high-coverage regions from deletion calls. chopsticks uses two parameters, k and f. the k parameter is a threshold used to distinguish high-coverage regions from low-coverage ones, and f determines the threshold of joint coverage of regions excluded from a deletion call. see methods for details. our implementation of chopsticks is available on the internet.. computational experiment to evaluate the power of chopsticks in improving the resolution of deletion calls, we conducted computational experiments. let the upstream difference of a deletion call be x−y, where x is the position of the upstream end of the true deletion and y be that of the deletion call. similarly, let the downstream difference of a deletion call be y′−x′, where x′ is the position of the downstream end of the true deletion and y′is that of the deletion call. by definition, the closer to zero a difference is, the better. a positive difference value indicates that the called breakpoint is outside the true deletion, whereas a negative value indicates that it is inside the true deletion. to evaluate chopsticks, the results of chopsticks have to be compared with the positions of true deletions. therefore we need ngs reads of a genome whose svs against the reference genome are known up to bp-level resolution. we conducted two experiments described below. simulated reads in the first experiment, we evaluated chopsticks with simulated ngs reads for which all svs were known up to bp-level resolution. to obtain data as realistic as possible, we generated a genome sequence with svs and simulated ngs sequences by using sv annotations published by quinlan et al.. the accession number of the sv annotations is. first, we deleted regions of the reference genome sequence that were annotated as deletions by quinlan et al. next, we inserted random fragments whose number and distribution of lengths were the same as annotated deletions, assuming that deletions and insertions are symmetric. then, we introduced single nucleotide substitutions into the simulated genome sequence and generated paired reads from it. we conducted this simulation and evaluation of chopsticks for chromosome of the reference mouse genome mm all paired reads were mapped to mm using burrows-wheeler aligner. then we conducted sv analysis by using sv detection tools from each of categories described in the background section: breakdancer of threshold-based rp methods, modil of distribution-based rp methods, clever of graph-based rp methods, cnvnator of rd methods, and pindel of sr methods. after that, we applied chopsticks to their results. before applying chopsticks, we examined the ability of sv detection tools to detect deletions in chromosome of the simulated mouse genome. we say that a deletion call is correct if it overlaps exactly one true deletion while the true deletion in turn overlaps exactly one deletion call. we show the number of called and correct sv calls in table we also show their recall and precision in figure the recall of breakdancer and clever was relatively good for all of tried coverage values, whereas the recall of pindel was satisfactory only when coverage was high. the recall of modil was low for all coverage values tried. although almost all deletions called by these methods were correct, cnvnator generated numerous false positives. because chopsticks is developed to correct breakpoints outside true deletions, we counted the number of deletion calls that cover the whole of true deletions. as shown in figure most of the deletion calls by modil, cnvnator, and pindel covered the whole of true deletions. however, a significant portion of breakdancer and clever results did not cover the whole of true deletions. note that chopsticks is harmless to these deletion calls because chopsticks does not trim them when there are no alignments in true deletions. results of deletion calls by breakdancer, modil, clever, cnvnator, and pindel. the values to the left of ”/” are the numbers of correct deletion calls, where a correct deletion call is the one that overlaps with exactly one true deletion, which, in turn, only overlaps with the deletion call; the values to the right of ”/” are the numbers of all deletion calls. breakdancer and clever results were good in both sensitivity and specificity. cnvnator generated numerous false positives, while pindel suffered from low coverage. modil missed lots of deletions. next, we applied chopsticks to the results of sv detection tools. after that, we examined how well the resolution of deletion calls was improved. we tested chopsticks for k=,…, and f=,,…,. we evaluated differences at both the upstream and downstream ends of deletions, and found that the results were similar. therefore we only present the results at upstream ends. resolution improvements for breakdancer deletion calls as shown in figure the resolution of deletion calls was clearly improved by using chopsticks. the original breakdancer results was successfully corrected, which is also clear in figure when coverage was low, the resolution was well improved for small k values. when coverage was high, the resolution was also improved for large k values. therefore, when the coverage is high, we recommend using large k values to ignore erroneous alignments. as shown in figure chopsticks worked well regardless of deletion lengths. resolution improvements for modil deletion calls as shown in figure the resolution of deletion calls by modil was also improved by using chopsticks. we omitted evaluation of modil for coverage= because modil was very slow. resolution improvements for clever deletion calls the resolution of deletion calls by clever was also improved by using chopsticks. as mentioned above, deletion calls of clever do not always cover the whole of true deletions. nonetheless, as shown in figure and chopsticks successfully improved resolution of clever results by selectively correcting predicted breakpoints outside true deletions. resolution improvements for cnvnator deletion calls because rd methods call svs by examining coverages in windows of a fixed size, the positions of breakpoints predicted by the rd methods have unavoidable ambiguity and they might be either inside or outside true deletions. because chopsticks assumes that predicted breakpoints are outside true deletions, we applied chopsticks after we expanded deletion calls of cnvnator at both ends by the window size. as shown in figure the results of cnvnator were successfully improved. this result indicates that chopsticks is also available for rd methods in addition to rp methods. results of chopsticks applied to pindel deletion calls owing to the sr signature that allows pindel to detect svs at bp-level resolution, the positions of breakpoints obtained with pindel were quite accurate. when chopsticks was applied to the results of pindel, the results became slightly worse than the original pindel results, as shown in figure although differences remained close to zero in most cases. note that the recall of pindel was not satisfactory when coverage is low, as shown in figure chopsticks is useful in cases where deletions missed by pindel are analyzed. real illumina reads of dba/2j in the second experiment, we evaluated chopsticks using the real ngs sequences of quinlan et al.. the sample was taken from a female mouse of the dba/2j strain, whose genome contains svs against the reference genome of the c57bl/6j strain. the read sequences were available from the ncbi sequence read archive database. the accession number of the read sequences is. to evaluate the results of chopsticks, we need bp-level sv annotations of dba/2j as well. therefore we generated deletion calls at bp-level resolution using sanger reads in a manner similar to that of quinlan et al. see methods for details. our deletion calls are available at the dbvar database under accession no.. we tried the five sv detection tools used in the previous experiment, and found that modil, cnvnator and pindel missed the most of deletions detected with sanger reads. these methods seemed to suffer from the low depth of coverage and short read lengths. therefore, we hereafter only describe results of chopsticks applied to breakdancer and clever results. resolution improvements for breakdancer deletion calls resolution improvements for clever deletion calls clever detected much more deletions than breakdancer. the results of clever were also improved by chopsticks as shown in figure where the peak around zero became stronger. however, it was difficult for chopsticks to correct positions of breakpoints when they were away from those predicted with sanger reads by hundreds of bases.  we have presented a new method called chopsticks to improve the resolution of predicted positions of deletions. the key idea is to exploit both concordant read pairs and discordant ones. according to our theoretical analysis, the resolution of our method is quite similar to that of threshold-based rp methods but with double coverage. in an experiment on simulated ngs reads, chopsticks clearly improved the results of breakdancer, modil, clever, and cnvnator. although the resolution of pindel results is quite high, chopsticks works well even for low-coverage data where recall of pindel is not sufficient. the effectiveness of chopsticks was also confirmed by performing an experiment on real illumina reads. despite a number of methods proposed for detecting svs, there is no one-stop method that simultaneously achieves high sensitivity, high specificity, high resolution, and robustness for low-coverage data. therefore a combination of sv detection methods is required, and chopsticks can play an important role because it uses new independent information ignored in other methods. as a future work, we consider to develop a method to distinguish homozygous deletions from heterozygous ones and to apply chopsticks to the former. with this approach, chopsticks will be available for more applications. 
to understand their functional impact or to infer molecular mechanisms of svs, they have to be characterized with the maximum resolution. chopsticks can generate high-resolution deletion calls of homozygous deletions using information independent of other methods, and it is therefore useful to examine the functional impact of svs or to infer sv generation mechanisms. we propose a new method called chopsticks that improves the resolution of sv detection for homozygous deletions even when the depth of coverage is low. conventional methods based on read pairs use only discordant pairs to localize the positions of deletions, where a discordant pair is a read pair whose alignment has an aberrant strand or distance. we theoretically proved that when the depth of coverage approaches zero or infinity, the expected resolution of our method is asymptotically equal to that of methods based only on discordant pairs under double coverage. however, high-resolution analysis is a difficult task because it requires investigation of the complex structures involved in an enormous number of alignments of next-generation sequencing reads and genome sequences that contain errors. to confirm the effectiveness of chopsticks, we conducted computational experiments against both simulated ngs reads and real ngs sequences. structural variations in genomes are commonly observed even in healthy individuals and play key roles in biological functions. the resolution of deletion calls by other methods was significantly improved, thus demonstrating the usefulness of chopsticks.
 structural variations in genomes are commonly observed even in healthy individuals and play key roles in biological functions. to understand their functional impact or to infer molecular mechanisms of svs, they have to be characterized with the maximum resolution. however, high-resolution analysis is a difficult task because it requires investigation of the complex structures involved in an enormous number of alignments of next-generation sequencing reads and genome sequences that contain errors.  we propose a new method called chopsticks that improves the resolution of sv detection for homozygous deletions even when the depth of coverage is low. conventional methods based on read pairs use only discordant pairs to localize the positions of deletions, where a discordant pair is a read pair whose alignment has an aberrant strand or distance. in contrast, our method exploits concordant reads as well. we theoretically proved that when the depth of coverage approaches zero or infinity, the expected resolution of our method is asymptotically equal to that of methods based only on discordant pairs under double coverage. to confirm the effectiveness of chopsticks, we conducted computational experiments against both simulated ngs reads and real ngs sequences. the resolution of deletion calls by other methods was significantly improved, thus demonstrating the usefulness of chopsticks.  chopsticks can generate high-resolution deletion calls of homozygous deletions using information independent of other methods, and it is therefore useful to examine the functional impact of svs or to infer sv generation mechanisms. 