Email updates

Keep up to date with the latest news and content from Genome Biology and BioMed Central.

Open Access Highly Accessed Method

An integrative probabilistic model for identification of structural variation in sequencing data

Suzanne S Sindi12*, Selim Önal3, Luke C Peng3, Hsin-Ta Wu13 and Benjamin J Raphael13*

Author affiliations

1 Center for Computational Molecular Biology, Brown University, Box 1910, Providence, RI 02912, USA

2 Department for Molecular Biology, Cellular Biology and Biochemistry, Brown University, 185 Meeting St, Providence, RI 02912, USA

3 Department of Computer Science, Brown University, 115 Waterman St. Providence, RI 20912, USA

For all author emails, please log on.

Citation and License

Genome Biology 2012, 13:R22  doi:10.1186/gb-2012-13-3-r22

The electronic version of this article is the complete one and can be found online at: http://genomebiology.com/2012/13/3/R22


Received:26 October 2011
Revisions received:5 March 2012
Accepted:27 March 2012
Published:27 March 2012

© 2012 Sindi et al.; licensee BioMed Central Ltd.

This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Paired-end sequencing is a common approach for identifying structural variation (SV) in genomes. Discrepancies between the observed and expected alignments indicate potential SVs. Most SV detection algorithms use only one of the possible signals and ignore reads with multiple alignments. This results in reduced sensitivity to detect SVs, especially in repetitive regions. We introduce GASVPro, an algorithm combining both paired read and read depth signals into a probabilistic model that can analyze multiple alignments of reads. GASVPro outperforms existing methods with a 50 to 90% improvement in specificity on deletions and a 50% improvement on inversions. GASVPro is available at

    http://compbio.cs.brown.edu/software
.

Background

Structural variation, including duplications, deletions and rearrangements of large blocks of DNA sequence, is now recognized as an important contributor to the genetic differences between individual humans and the somatic differences between normal and cancer cells [1-7]. It is also prevalent in other organisms, including many model organisms [8-10]. Knowledge about the extent of structural variation has increased rapidly in the past few years with improvements in DNA microarray and sequencing technologies. In particular, sequencing approaches identify all types of structural variation, including copy number variants and balanced rearrangements like inversions and reciprocal translocations [11-13]. While next generation sequencing technologies are now widely used to assess both genetic variation in normal genomes [14-21] and somatic structural variation in cancer genomes [4,7,22,23], the short reads and short inserts of these technologies make the identification of many structural variants (SVs) non-trivial. Since de novo assembly of mammalian genomes from next-generation sequencing technologies remains a challenge [24,25], many SVs are identified using a resequencing approach where sequence reads from an individual genome are aligned to a reference human genome assembly. The resequencing approach thus leverages the extensive finishing efforts employed in the generation of the human reference genome.

Many strategies have been employed to predict structural variation using the resequencing approach [11-13]. First, read depth (RD), the density of mapped reads to an interval of the reference genome, has been used successfully to identify copy number variants [26-31]. However, RD is unable to detect copy neutral variants such as inversions and balanced translocations. Second, paired read (PR) approaches have been used to identify all types of SVs, both copy number variants and copy-neutral variants [16,28,32-35]. These approaches analyze the collection of PR mappings and find clusters of aberrantly mapped PRs that suggest SVs distinguishing the two genomes. Third, split read (SR) methods have been employed to directly identify sequence reads that contain breakpoints of SVs [36]. However, the short reads produced by current second-generation sequencing technologies have limited the use of SRs for SV detection; for example, Ye et al. [36] rely on anchoring the search for SRs using a full-length alignment of one read from a PR.

While there has been extensive development of methods for structural variation prediction, there remains room for improvement. First, most existing methods for SV prediction use only one of the possible signals (RD, PR or SR). A few methods employ a second signal in later post-processing of predictions. Such a post hoc approach may improve specificity, but it does not increase sensitivity by combining multiple, weak signals. Although a few recent methods have begun to consider both RD and PR signals [37,38], these methods have focused only on copy number variants. Second, most methods for structural variation prediction used only reads with unique high-confidence alignments to the reference genome, ignoring reads with lower quality alignments or multiple possible alignments [32,33,39]. As such, these methods have very low sensitivity to detect repeat-associated rearrangements. Since many SVs are associated with repetitive sequences, including segmental duplications [40], and mobile elements [2], a substantial improvement in sensitivity may be possible by including reads with multiple alignments. More recently, a few methods have been introduced that consider multiple or lower quality alignments of reads relying on various criteria to select among possible candidate alignments [34,41,42]. While these methods may predict more true variants, this increased sensitivity often comes at the cost of reduced specificity as these methods produce many false positive predictions. Thus, there is a need for additional improvements in sensitivity and specificity for SV prediction. For example, the pilot study of the 1000 Genomes Project did not report inversion SVs [43] even though such variants have been previously shown to be abundant in normal genomes [16].

Here, we introduce GASVPro, an algorithm for SV identification that integrates both RD and PR signals into a unified probabilistic model. We find that the likelihood of a predicted variant under our probabilistic model provides a better criteria for prioritizing predictions than the number of supporting PRs, a common heuristic for ranking predictions. In addition to combining both RD and PR signals, GASVPro explicitly reports uncertainty in each predicted breakpoint, which is useful information for identification of SRs or designing assays for experimental validation. This breakpoint localization is obtained using a computational geometric algorithm, Geometric Analysis of Structural Variants (GASV) [33], that represents all possible breakpoints, or breakends, that are consistent with the aligned reads as a polygon in two-dimensional genome space. By carefully clustering only those PRs that genuinely support the same breakends, GASV avoids over-collapsing fragments into the same SV prediction, a problem demonstrated in other methods (see Results) and reports coordinates consistent with the true variant points.

Moreover, GASVPro exploits this explicit representation of the breakends to incorporate a subtle signal of highly localized drops in coverage at the variant breakends. We call this signal breakend read depth (beRD), and it occurs for both copy number variants as well as copy-neutral SVs. Using this signal, GASVPro predicts whether a generic breakend is a homozygous or a heterozygous variant, even when relatively few PRs support the variant. Thus, GASVPro is the first method to utilize RD to predict generic SVs, including inversions and reciprocal translocations, and not just copy number variants. For deletions, GASVPro uses the stronger signal of RD across the entire deleted interval, and this combination of PR and RD leads to highly sensitive and specific deletion predictions. GASVPro also considers reads with multiple possible alignments, using a Markov chain Monte Carlo (MCMC) approach to sample over the space of possible mappings for each paired-end sequenced fragment. In this way, GASVPro does not select only a single 'best' alignment for each fragment, but rather computes a posterior probability of each variant over all possible alignments of each read.

We demonstrate the advantages of GASVPro on simulated data and Illumina sequencing data from two sequenced human genomes, NA18507 [14] and NA12878 [44] (1000 Genomes Project). We compare predictions to known variants with a novel metric, the 'double uncertainty' metric, developed to allow for unambiguous comparisons when there is uncertainty in the breakpoint locations. For deletions, GASVPro outperformed competing methods by attaining equal or greater sensitivity while making at least 50% and up to 90% fewer predictions. In addition, on a subset of deletions with known ploidy, GASVPro successfully classifies over 85% as homozygous or heterozygous. For inversions, GASVPro is up to twice as specific at maximum sensitivity than existing methods. In particular, because of GASVPro's use of the beRD signal, it is the only method to attain optimal specificity and sensitivity on our simulated data set. In other cases, GASVPro's use of the beRD signal at inversion breakpoints results in equal or better specificity than competing methods despite considering a larger set of possible alignments.

Results

A probabilistic model of structural variant breakends

Identifying structural variants from paired-read sequencing data

In PR mapping, fragments from a test genome are sequenced from both ends and the resulting PRs are aligned to a reference genome. The goal of the alignment process is to determine the correct mapping of the fragment, that is, the corresponding position of the fragment in the reference genome (Figure 1a). For now, we assume that all reads have a single high-quality alignment to the reference, which corresponds to its mapping, and consider the problem of reads with multiple alignments later.

thumbnailFigure 1. Signals of structural variation from paired-end sequencing. (a) Fragments (black arches) from a test genome are sequenced from both ends and the resulting paired reads are mapped to a reference genome. Fragments containing the breakpoint of a structural variant (black arches with arrows) have a discordant mapping (red). (b) The GASV program [33] efficiently clusters discordant fragments supporting the same variant and provides precise information about the localization of the adjacency, (a,b), created by the rearrangement. For example, on the left a deletion of the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M269','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M269">View MathML</a> from the reference creates a novel adjacency <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M270','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M270">View MathML</a> of breakends <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M271','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M271">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M272','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M272">View MathML</a>. GASV represents the novel adjacency as a breakend polygon (shaded red trapezoid) where the left and right breakends of the variant must lie within the breakend polygon. In this example, we show breakend polygons for a deletion (left) and an inversion (right), each supported by two discordant fragments. (c) The presence of a structural variant is also indicated by changes in the depth of coverage of concordant mappings. For the deletion (left) the depth of coverage is low throughout the entire region, while for the inversion (right) the depth of coverage drops only near the breakends.

Although the length of each individual fragment is generally unknown, the size selection that is performed during the construction of the sequencing library yields an approximate distribution of fragment lengths. We assume that fragment lengths are between <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M1">View MathML</a>and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M2">View MathML</a>; these values can be derived from the empirical distribution of mapped fragments. Fragments with both ends mapping uniquely to the reference with 'convergent orientation' and with mapped distance in the range <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M3">View MathML</a> are called concordant fragments because their mapping indicates concordance (no SV) between the test and reference genome. (We note that the definition of convergent orientation depends on sequencing technology. For example, with Illumina paired-end data, the reads are obtained from opposite DNA strands and thus convergent orientation is defined as reads with opposite orientation, with the left read forward and the right reversed (+/-). With SOLiD paired-end data, reads are obtained from the same DNA strand and thus should have the same orientation. In this case, convergent orientation is defined as reads with positive orientation when the first sequenced has smallest mapped coordinate (+/+) and negative orientation when the first sequenced read has largest mapped coordinate (-/-).) The remaining discordant fragments indicate potential SVs or sequencing/alignment errors.

Although researchers typically focus on common classes of SVs, such as deletions and inversions, more generally a SV corresponds to a rearrangement creating one or more novel adjacencies between pairs of locations in the reference genome. That is, two locations a and b, which were originally separated in the reference genome, are now adjacent in the test genome. For example, a deletion creates one novel adjacency while an inversion creates two (Figure 1a). Following the terminology of VCF (Variant Call Format) version 4.1 [45], we refer to locations a and b individually as breakends and as mated breakends when paired at either end of a SV created by a rearrangement.

We define a predicted SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> as a pair <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M5">View MathML</a> where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M6">View MathML</a> is a set of k discordant fragments containing the novel adjacency, and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M7">View MathML</a> is the breakend polygon, a region describing all possible mated breakends (a,b) determined by the discordant fragment mappings (Figure 1b). The breakend polygon is defined by the positions of the mapped ends of each fragment and the minimum (<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M8">View MathML</a>) and maximum (<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M9">View MathML</a>) length of fragments. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is a true SV, then there is an ordered pair <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M10">View MathML</a> corresponding to a novel adjacency created by the rearrangement. That is, there is a <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M11">View MathML</a> such that a and b are the breakends of the SV in the reference genome. (See Materials and methods and [33] for more information on how the breakend polygon is defined.)

Discordant and concordant fragments provide complementary information about a variant. Discordant fragments define the breakend polygon <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M7">View MathML</a> while concordant fragments (or lack thereof) provide additional information about the precise location of the breakends within the polygon. If a and b represent mated breakends created by a deletion, inversion or other rearrangement in the reference genome, we should see a decrease in the coverage by concordant fragments at these points. The type of signal we expect to see depends on the type of SV present (Figure 1c). For a deletion, we expect a drop in the coverage of concordant fragments throughout the genomic interval [a,b]. This is commonly known as the RD signal and has previously been exploited to reveal copy number variants [38]. For an inversion or reciprocal translocation, we expect a sharp drop in coverage in the regions immediately surrounding a and b as many of the fragments containing a or b in the test genome are discordant when mapped to the reference. However, there is no drop in coverage 'inside' the inversion or translocation. We define this highly local drop in coverage as the breakend read depth (beRD) signal.

We develop a probabilistic model based upon the mapped locations of all fragments, concordant and discordant, in the test genome. By doing so we integrate both the presence of discordant fragments (PR signal) and concordant coverage (RD signal) into a single probabilistic method, GASVPro. In addition, GASVPro directly estimates the location of the breakends a and b for a SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> and classifies the prediction as homozygous or heterozygous. We first present our model in the restricted context where every fragment has a unique mapping to the reference genome. Then, we extend our model to fragments with multiple alignments by using an MCMC approach to sample over the possible mappings for each fragment.

Probability of a structural variant

We determine the probability of a potential SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> by considering the number, k, of discordant fragments as well as the beRD, the depth of coverage at each candidate breakend. By doing so, we directly estimate the novel adjacency created by <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> by considering all possible mated breakends consistent with the discordant fragments. Since our formulation depends only on the process of sampling fragments from the test genome, and not on the class of variant, our probabilistic model is applicable to generic rearrangements.

We follow the Langer-Waterman model [46] of sequencing and assume that the starting positions of the fragments are sampled from the test genome uniformly so that the left positions of fragments follow a Poisson process with parameter λ. If all sequenced fragments had fixed length L, the number of fragments containing an arbitrary point p from the test genome, called the coverage of p, would simply be the number of fragments sampled with left endpoint in the interval [p - L + 1,p]. According to the Poisson process, the coverage of a point p follows a Poisson distribution with mean λL. In general, we do not know the size of any particular fragment and thus we use the average fragment length, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M12">View MathML</a>, and model the coverage of p by a Poisson distribution with mean <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M13">View MathML</a>.

If p is sufficiently far from all sites of structural variation, we expect all sequenced fragments containing p to be concordant with respect to the reference genome. However, if p is the breakend of an SV, coverage will be reduced, as there will be fewer concordant fragments containing the breakend. In particular, the distribution of the number of fragments containing a breakend p is approximated by a Poisson distribution with mean <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M14">View MathML</a> (see Materials and methods and Figure A1 in Additional file 1).

Additional file 1. An Appendix containing additional figures, discussion of MCMC properties and comparison of clustering methods.

Format: PDF Size: 572KB Download file

This file can be viewed with: Adobe Acrobat ReaderOpen Data

Consider a candidate SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M15">View MathML</a>. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is a true SV, then there is an ordered pair, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M16">View MathML</a>, corresponding to a novel adjacency in the test genome created by the rearrangement. As such, the number of concordant fragments containing a or b should be lower than expected for an arbitrary point in the reference genome. Alternatively, if <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is not a true SV, then the coverage of points a and b by concordant fragments will follow the Poisson distribution with mean <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M17">View MathML</a>. We next describe the probability of a variant <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> by conditioning on the choice of breakends and number of copies of the novel adjacency (a,b) in the test genome. Specifically, for a candidate novel adjacency <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M18">View MathML</a>, let C(a,b) = {0,1,2} indicate the number of copies of the novel adjacency in the test genome. (Here we are considering only copy-neutral or copy number loss events (for example, deletions) and not duplications. The extension to the latter case is future work.) We consider three events: (1) a and b are breakends of a homozygous SV, (C(a,b) = 2); (2) a and b are breakends of a heterozygous SV (C(a,b) = 1); (3) a and b are not SV breakends (C(a,b) = 0).

For a candidate breakend p, we define the breakend read depth (beRD), n(p), to be the number of mapped fragments containing p. In the case that a and b are endpoints of a homozygous SV, we expect n(a) = n(b) = 0; that is, any concordant fragment containing a or b represents a mapping error. We assume that mapping errors are independent and the probability, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M19">View MathML</a>, of an erroneous mapping is the same for all fragments. In addition, the number, k, of discordant fragments in <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M20">View MathML</a> is drawn from a Poisson distribution with parameter <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M21">View MathML</a>. Thus, conditional on a choice of breakends (a,b), the probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> represents a homozygous SV (that is, C(a,b) = 2) is given by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M22">View MathML</a>

(1)

where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M23">View MathML</a> is the probability density function for the Poisson distribution with mean λ. One could explicitly define the unconditional probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is a homozygous variant by examining the likelihood that each pair <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M24">View MathML</a>are the true mated breakends. Instead, we make a simplification by taking the maximum probability over all possible breakend pairs:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M25">View MathML</a>

(2)

where by C(B) = 2 we mean the breakpoint region <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M7">View MathML</a> defines a homozygous SV.

Similarly, if <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M26">View MathML</a> are mated breakends of a heterozygous variant, C(a,b) = 1, we expect the number of concordant fragments that contain a or b to follow a Poisson distribution with mean <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M27">View MathML</a> and the number of discordant fragments that contain the novel adjacency (a,b) to follow a Poisson distribution with mean <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M28">View MathML</a>, respectively. Thus, conditional on the choice of breakends (a,b), the probability that V represents a heterozygous SV is given by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M29">View MathML</a>

(3)

As before, we define the unconditional probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> represents a heterozygous variant by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M30">View MathML</a>

(4)

Finally, if a and b, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M31">View MathML</a>, are not breakends of a SV, C(a,b) = 0, we expect the number of concordant fragments containing the breakpoints n(a) and n(b) to follow Poisson distributions with mean λc and all k discordant fragments to be mapping errors, each occurring independently with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M32">View MathML</a>. Thus, conditional on a choice of (a,b), the probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> does not represent a SV is given by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M33">View MathML</a>

(5)

As before, we define the unconditional probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is not a variant by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M34">View MathML</a>

(6)

For each candidate variant we decide between alternatives using a likelihood ratio. That is, we compare the probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> represents a SV (homozygous or heterozygous) with the probability that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> is an error as follows:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M35">View MathML</a>

(7)

In practice we report variants <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a> where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M36">View MathML</a> exceeds a prescribed threshold. In addition to assigning a likelihood to a SV, our formulation determines a maximum likelihood estimate for the novel adjacency (a,b) and if a variant is homozygous or heterozygous.

Probability of a deletion

The model in the previous section presented considers only coverage at the breakends a and b. However, deletions have a stronger signal of reduced coverage, as shown in Figure 1c. That is, for a true deletion coverage by concordant fragments should be reduced throughout the entire deleted segment. Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M37">View MathML</a> be a predicted deletion supported by k discordant fragments and define <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M38">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M39">View MathML</a>. Then, for any choice of mated breakends <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M40">View MathML</a>, the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M41">View MathML</a> must be deleted. As before, we expect the number n(I) of concordant fragments whose mappings overlap the interval I(B) to be Poisson distributed with mean:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M42">View MathML</a>

Let C(B) = {0,1,2} be the number of copies of the variant in the test genome. We consider the probability of three events:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M43">View MathML</a>

and finally the likelihood of a deletion compared to a mapping error:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M44">View MathML</a>

(8)

There are several additional factors we consider when using our model on sequencing data. First, there are factors other than SVs that can impact the coverage of concordant fragments over an interval. As such, to adjust for differences in the ability to map reads throughout the genome, in our model for deletions we scale the number of concordant fragments by the local mapability of the putative deleted interval. Second, since in this study we are primarily interested in inversion and deletion SVs, in practice we utilize a heuristic to eliminate regions of the genome with extremely high coverage by concordant fragments. Further information on these practical details are given in the Materials and methods section.

Selecting a mapping for each fragment

In the previous sections, we assumed that there was a single high-quality alignment for all reads and therefore one high-quality alignment for each fragment. However, some reads may have multiple high-quality alignments due to repetitive sequences in the reference or sequencing errors in the reads. Selecting one of the possible alignments for each read from the pair defines an alignment of the fragment. Since each fragment represents a unique contiguous region of the test genome, at most one alignment is the correct one and we refer to this as the mapping of the fragment.

Selecting a mapping for each fragment defines the set of concordant and discordant fragments and an associated set of SVs that could be evaluated using the model in the previous section. Although any such selection defines a fragment configuration consistent with the data, each selection has a different probability. Thus, rather than selecting a mapping for each fragment in advance, we consider the space of all possible mappings for all fragments and use a MCMC approach to sample from the space of possible mappings in proportion to their probability.

With these distinctions, we now revisit our notions of 'concordant' and 'discordant' from above. A concordant fragment is a fragment whose unique mapping is concordant. That is, both reads have a single high-quality alignment to the reference and the alignments are concordant with respect to the sequencing process. A discordant fragment is a fragment whose entire set of alignments are discordant. (Note, this formulation ignores any fragment with multiple alignments, at least one of which is concordant.)

Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M45">View MathML</a> be the set of all discordant fragments. Suppose that the two reads from a fragment <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M46">View MathML</a> map to s and t locations, respectively. An alignment of a fragment corresponds to selecting an alignment for each read, and thus we define <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M47">View MathML</a> where i = 1,2,...s and j = 1,2,...t as the set of all alignments for a fragment <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M48">View MathML</a>, only one of which may be the true mapping. Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M49">View MathML</a> be the set of alignments for all fragments.

Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M50">View MathML</a> be a set of candidate SVs supported by <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M51">View MathML</a>, as before <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M52">View MathML</a>. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M53">View MathML</a> is computed by clustering discordant pairs that support the same variant. (In the results below, we use GASV [33] to obtain the breakpoint polygon associated with each <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M54">View MathML</a>; however, this step could be replaced by a different clustering method.) We represent the set of all possible SVs supported by <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M55">View MathML</a> with an m×n binary (0-1 valued) alignment matrix, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M56">View MathML</a>, with rows corresponding to fragments <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M57">View MathML</a> and columns corresponding to possible SVs <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M58">View MathML</a>. Here <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M59">View MathML</a> if fragment <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M60">View MathML</a> supports SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M61">View MathML</a> (that is, there is an element of <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M62">View MathML</a> that supports variant <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M63">View MathML</a> and thus <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M64">View MathML</a>) and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M65">View MathML</a> otherwise (Figure 2).

thumbnailFigure 2. Overview of the GASVPro. Fragments <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M273','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M273">View MathML</a> from a test genome are sequenced and the resulting paired reads are aligned to the reference. A fragment may either have a unique mapping or be ambiguous with multiple alignments to the reference. Following clustering of alignments (with GASV), the set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M274','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M274">View MathML</a> of possible structural variants and the fragments whose alignments support these variants are recorded in the alignment matrix A. As each fragment originates from a single location in the test genome, a fragment supports at most one structural variant. Thus, the mapping matrix M records the 'true' mapping for each fragment. GASVPro scores mapping matrices according to a generative probabilistic model that incorporates concordant mappings. GASVPro utilizes an MCMC procedure to efficiently sample over the space of possible mapping matrices defined by the alignment matrix A. The underlying probabilistic model can be easily generalized to consider additional features indicative of a 'true' mapping, such as the empirical fragment length distribution or probability of sequencing errors.

We assume that a discordant fragment supports at most one SV. Thus, our goal is to select the single 'correct' mapping for each fragment, according to some criterion. Such a selection corresponds to a binary <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M66">View MathML</a> mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M67">View MathML</a>, where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M68">View MathML</a> if fragment <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M69">View MathML</a> is assigned to SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M70">View MathML</a>. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M71">View MathML</a> satisfies the following:

1. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M72">View MathML</a>; that is, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M73">View MathML</a> only if <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M74">View MathML</a>,

2. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M75">View MathML</a>for all i; that is, each row in <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> has at most one non-zero entry.

Finally, as before, the probability of variants depends on the associated copy number, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M77">View MathML</a>, of a variant. We explicitly distinguish between homozygous and heterozygous SVs by including a binary vector <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M78">View MathML</a> where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M79">View MathML</a>. If any discordant fragments are assigned to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M80">View MathML</a>, we require <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M81">View MathML</a>. Together <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M82">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> define the differences between the test and reference genome.

Probability of a mapping matrix

Our data D consists of a set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M83">View MathML</a> of discordant fragments, a set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M84">View MathML</a> of alignments, a set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M85">View MathML</a> of possible SVs, and the positions of all concordant mappings in the genome. We next generalize our probability model from the previous section to the probability of a mapping matrix based on the generation of the data D from a given genome.

For a mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> and discordant fragment <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M86">View MathML</a>, let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M87">View MathML</a> denote the column index of the 1 in the i-th row, or 0 if <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M88">View MathML</a> is not assigned. For a mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> and a variant <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M89">View MathML</a>, let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M90">View MathML</a> be the set of rows with a 1 in column j. The support, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M91">View MathML</a>, of variant j is defined as the number of assigned discordant fragments:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M92">View MathML</a>

Finally, we define the total number of variants <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M93">View MathML</a> predicted by <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a>:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M94">View MathML</a>

Given an alignment matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M95">View MathML</a>, the probability of a mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> is a function of the number of fragments supporting each variant with positive support. We assume that the number of variants with positive support follows an exponential distribution with parameter <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M96">View MathML</a>. Finally, if a discordant fragment is assigned to none of the SVs, then this fragment represents a mapping error, an event with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M97">View MathML</a>. Thus, we have:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M98">View MathML</a>

(9)

where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M99">View MathML</a> is the SV in column j supported by fragments <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M100">View MathML</a>, corresponding breakpoint region <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M101">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M102">View MathML</a>. As above, we utilize a different model for predicting deletions that also includes read depth inside the putative deleted interval. Finally, we define <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M103">View MathML</a> by defining <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M104">View MathML</a> by selecting the most likely copy number <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M105">View MathML</a> for each j:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M106">View MathML</a>

(10)

Note that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> specifies a unique mapping for each fragment supporting a variant; thus, one solution would be to consider <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M107">View MathML</a> over all possible mapping matrices. However, because the number of possible mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> grows exponentially with the number of fragments, we use a MCMC procedure to efficiently sample from the space possible mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> (Figure 2; Section A2 and Figures A2, A3 in Additional file 1). Our MCMC procedure converges to the unique stationary distribution given in Equation 10.

Although the space of mapping matrices has high dimension, our MCMC procedure remains computationally tractable because our sampling procedure may be performed on disjoint sets of fragment mappings and the variants they support. Thus, our MCMC samples independently on each such component and the combination of these samples converges to the same stationary distribution as sampling over the complete space. See Figure 3 for a schematic. In the Materials and methods section, we provide a complete description of our MCMC sampling procedure and provide further discussion in Additional file 1.

thumbnailFigure 3. Sampling over connected components of alignments. The probabilistic model P(M|A) used by GASVPro allows for efficient decomposition of the original space of mapping matrices M into independent components. Thus, we sample using MCMC on each component independently and merge the results.

Deriving the predicted structural variants

Our MCMC procedure samples mapping matrices in proportion to their probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M108">View MathML</a>; however, our ultimate goal is to report a final set of SV predictions. One approach to SV prediction is to select a single <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> according to some criteria; for example, the <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> that minimizes the total number of SVs predicted. This approach is used by a number of SV detection methods that consider multiple assignments for fragments, such as VariationHunter [42] and Hydra [34]. We instead predict SVs by considering the entire space of mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> according to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M109">View MathML</a> as described in the Materials and methods. In practice, we found only minor differences in the receiver operating characteristic (ROC) curves for the different reporting methods we considered (Figure A4 in Additional file 1).

Results on sequenced data

We applied GASVPro to simulated paired-end data on the Venter Genome (HuRef) [47], as well as two previously sequenced human genomes, NA18507 [14] and a European individual, NA12878, from the 1000 Genomes study [44]. We also compared results from GASVPro to two previously published methods, Hydra [34] and BreakDancer [32], as well as the original GASV. (We also performed some comparisons with VariationHunter [42]. Since results were strikingly similar to Hydra, as previously noted in [34], and we were unable to process the full datasets for NA12878 and NA18507 using the current publicly available distribution of VariantionHunter, we present only the results for Hydra.) Finally, we compare to CNVer, a method combining RD and PR to detect copy number variants [38].

These methods, and other similar SV prediction programs, typically employ several steps, including alignment of reads to the reference genome, predicting SVs from alignments, post-processing predictions (for example, pruning a set of predicted SVs to remove redundancy) and comparison to known variants. In an effort to directly compare the performance of the SV prediction algorithms, rather than the specific pre- and post-processing steps, we standardized the alignment, post-processing and comparison steps. In particular, we used the same read alignments for all methods. (Note this involved modifying the source code for Breakdancer to consider only a user-specified set of discordant fragments.) For GASVPro and Hydra, the methods that allow fragments to have multiple possible alignments, we realigned reads to the reference genome with Novoalign [48] and distinguish results on the full set of alignments (GASVPro and Hydra) from results on only the high-quality unique alignments (GASVPro-HQ or Hydra-HQ). Before comparing results, redundant predictions were removed with the same pruning procedure for each method (see Materials and methods).

We compare predictions to a known set of variants using the double uncertainty metric, a novel metric developed to represent uncertainties in the breakpoint locations for both the predictions and the known variants (see Materials and methods; Figures A5 and A6 in Additional file 1). We use a ROC type analysis to show the number of novel predictions and true positives for each method as a function of the number of supporting fragments (Hydra, Breakdancer, GASV), the predicted depth of coverage (CNVer) or the likelihood of a predicted variant (GASVPro). Note that in the results shown below, GASVPro-HQ and GASV consider the same set of high quality unique alignments and utilize the same clustering algorithm. As such, both methods have the same maximum sensitivity, but GASVPro-HQ has higher specificity due to our probabilistic model. On the other hand, GASVPro uses a larger set of alignments, including lower quality and ambiguous alignments, and as such GASVPro can achieve higher sensitivity than GASVPro-HQ and GASV.

Simulated data

We first test GASVPro on simulated data generated from the Venter genome [47]. We produced a synthetic dataset by inserting the list of annotated SVs on chromosome 17 of Venter's genome (8,801 deletions, 8,572 insertions and 4 inversions) into the human reference genome (hg18). These SVs varied in length from one to several thousands of bases. We simulated 100× coverage of this chromosome by 50-bp PRs with a mean fragment length of 200 bp and a standard deviation of 20 bp using the SAMtools wgsim program [49]. For all methods, the resulting sets of predictions were pruned and compared to known variants with the double uncertainty metric with reference uncertainty set to 0 (see Materials and methods).

The lengths of deletions that are readily predicted from PRs depend on fragment size [11]. To mirror the procedures used on the sequenced genomes, we only considered fragments with mapped length ≥<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M110">View MathML</a> (where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M111">View MathML</a>) as potential deletions. We compared predictions from all methods to the 124 deletions with length ≥125 bp. Figure 4 compares all methods on this data set; compared with GASV, Breakdancer and Hydra, GASVPro is over 50% more specific at maximum sensitivity.

thumbnailFigure 4. Simulated Venter chromosome 17. ROC curves comparing deletion predictions for Breakdancer, GASV, GASVPro-HQ, Hydra-HQ, CNVer, GASVPro and Hydra to the 124 deletions from Venter chromosome 17 with minimum deletion length 125 bp. All methods analyzed the same set of high-quality unique mappings; in addition, GASVPro and Hydra considered a set of lower-quality alignments, including ambiguous fragments with multiple alignments. Predictions of all methods were post-processed in an identical fashion and the resulting predictions were compared to the known coordinates for the Venter deletions according to the double uncertainty metric (see Methods).

All methods had greater sensitivity than CNVer, which made 218 predictions but detected only 3 deletions with the double uncertainty metric. The lower sensitivity of CNVer can be explained in part by internal filtering: the published code of CNVer reports only copy-number events that are larger then 1 kb, which eliminates all but 9 out of 124 simulated deletions. In addition, the reported coordinates from CNVer lie farther from true breakends, although the predicted deletion interval typically contains the true deletion. We note that 16 of 218 CNVer predictions completely contained a true deletion, including 5 of 9 deletions larger than 1 kb. Thus, some of the difficulties with CNVer result from how it merges potential copy-number variants before reporting a final set of predictions (Section A3 in Additional file 1).

We next discuss GASV compared with Breakdancer, Hydra and Hydra-HQ. Before removing redundant predictions by pruning, GASV predicts 648 deletions with at least one supporting fragment, which detects 60 Venter deletions. Thus, the maximum sensitivity is 48%. A common method to increase specificity is to increase the minimum number of supporting fragments for a prediction. As discussed previously, however, many predictions from SV methods overlap. Removing these overlapping predictions (see Materials and methods) improves performance more than increasing the number of supporting fragments. For GASV, restricting the set of predictions to those with at least two supporting fragments results in 244 predictions but detects only 46 deletions. In comparison, pruning the 648 predicted deletions with at least one fragment retains 347 predictions that detect 57 true deletions. In comparison, Hydra-HQ and Hydra had slightly lower sensitivity, predicting only 44 deletions at maximum sensitivity, but had similar overall performance to GASV. Breakdancer had similar performance throughout with slightly higher sensitivity than Hydra/Hydra-HQ and GASV and equal specificity.

The integrative probabilistic model used by GASVPro greatly improves specificity. Analyzing only high quality unique mappings, GASVPro-HQ predicts only 64 deletions with positive log likelihood, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M112">View MathML</a>> 0, which include 50 true deletions. Note that these 64 predictions are a subset of those predicted by GASV. Thus, compared to GASV, GASVPro-HQ has a substantially lower false positive rate at highest sensitivity. The improved specificity of GASVPro-HQ over GASV is evidence that our likelihood statistic is a better predictor of true variants than the number of supporting fragments (see also Figure A7 in Additional file 1 for a comparison). Including low-quality and ambiguous alignments increases the space of possible variants substantially without significantly increasing the number of detectable deletions. That is, the full set of possible alignments suggest 1,051 potential deletion events that overlap, at most, 61 out of 124 true deletions. However, GASVPro has similar performance to GASVPro-HQ throughout. This suggests that the MCMC sampling method is able to successfully eliminate many false positive predictions even with a much larger number of initially possible variants.

Finally, we compared the ability of all methods to identify the four inversions on Venter chromosome 17 (Table 1). On this simulated data our probabilistic formulation and MCMC sampling method proved beneficial. GASVPro-HQ identified three inversions with four predictions while GASVPro identified all four inversions with no false positive predictions. Notably, the additional inversion identified by GASVPro had breakends within a segmental duplication. In this case a total of 170 fragments had two possible alignments, each of which corresponded to a potential inversion SV, but only one of which is the true inversion. The beRD signal used by GASVPro allowed the algorithm to successfully distinguish between the true and false prediction. The MCMC algorithm used by GASVPro assigned a greater likelihood to the true prediction because 23 concordant fragments map to the breakend polygon for the false prediction. In comparison, Hydra requires ten predictions to detect all four inversions. GASV and Breakdancer are slightly less sensitive, detecting only three quarters of known inversions. Thus, GASVPro is the only method to attain optimal sensitivity and specificity on the inversion data set.

Table 1. Comparison of performance of methods with respect to identifying the four inversions on Venter chromosome 17

Sequencing data

NA12878 deletions

We next compared the methods on Illumina sequencing data of a CEU individual, NA12878, from the 1000 Genomes Project. There are two sets of validated SVs available for this individual. First, deletions and inversions were validated from a previously published fosmid study [16] and deletions were separately validated as part of the 1000 Genomes Project [44]. In addition, the validated deletions from the 1000 Genomes data set were also annotated as homozygous or heterozygous.

Individual NA12878 was sequenced in both Pilot 1 (≈4× coverage) and Pilot 2 (≈40× coverage) of the 1000 Genomes Project. For Pilot 1, a single library was sequenced with a read length of 37 bp and an average fragment size of 230 bp. For Pilot 2, multiple libraries were sequenced with read lengths from 37 to 52 bp and an average fragment size of 150 to 350 bp. Thus, we analyzed both datasets to examine the effect of different coverage on the ability of methods to predict SVs.

In Figure 5 we plot 'ROC curves' comparing the predictions of GASV, GASVPro, GASVPro-HQ, Hydra, Hydra-HQ, CNVer and Breakdancer on data from Pilot 2 (Figure 5a,b) and Pilot 1 (Figure 5c,d) to both sets of validated deletions. Since CNVer could only be run on a single library, we consider CNVer results on Pilot 1 data alone. Because the complete list of true SVs in the genome is not yet known, we cannot compute the number of false positives/negatives. Thus, we plot the number of novel predictions compared to true positives. We also considered only predictions with at least two supporting fragments and plot these results as GASVPro-Min2. As before, to assess the difference due to low quality and ambiguous mappings, we plot both Hydra and Hydra-HQ; the latter is Hydra run on only high-quality uniquely mapped fragments.

thumbnailFigure 5. An 'ROC curve' comparing the number of known deletions that were correctly predicted (true positives) and the number of novel deletion predictions using sequencing data and validated deletions from the individual NA12878 in Pilot 1 and Pilot 2 of the 1000 Genomes Project. (As discussed in the Methods section, we separately considered two sets of validated deletions [16,44].)

We first consider the results on the higher coverage Pilot 2 data (Figure 5a,b). Four curves represent methods run on only uniquely mapped fragments: GASV, GASVPro-HQ, Hydra-HQ and Breakdancer. Breakdancer has slightly improved performance compared to Hydra-HQ and GASV, attaining equal sensitivity with up to 200 fewer predictions throughout. However, this may be an artifact of Breakdancer's aggressive clustering procedure (discussed in Section A3 of Additional file 1). GASVPro-HQ has the best overall performance with over a 85% reduction in novel predictions at highest sensitivity compared to Breakdancer, GASV and Hydra.

Of the three methods that use all alignments (GASVPro, GASVPro-Min2 and Hydra), GASVPro has the highest sensitivity, detecting 119 of 139 true deletions with 19,715 novel predictions on the set of validated deletions from the 1000 Genomes study. By increasing the minimum likelihood threshold, and thus reducing the number of predictions, GASVPro predicts 114 of 139 true deletions with only 907 novel predictions; this represents a 95% decrease in the number of novel predictions with only a 3% decrease in true positives. GASVPro-Min2 has higher specificity than GASVPro, making around 200 fewer predictions than GASVPro at equal sensitivity. Notice the addition of ambiguous mappings alone does not greatly improve performance as the behavior of Hydra and Hydra-HQ is very similar, with Hydra being slightly more sensitive. Thus, regardless of whether unique or ambiguous fragments are used, combining both read depth and PRs with our probabilistic model (GASVPro-HQ, GASVPro-Min2 or GASVPro) results in significant improvements to sensitivity and specificity.

In addition to improving the ability to successfully predict true deletions, our probabilistic model also accurately classifies these variants as homozygous or heterozygous. GASVPro-HQ correctly classified 104 out of the 119 known deletions with highest likelihood as homozygous or heterozygous according to the annotations in the 1000 Genomes data set. Remarkably, all 28 homozygous variants in this set were correctly classified even though some had fewer supporting discordant fragments than many correctly classified heterozygous variants.

On Pilot 1 data, we also compare the performance of CNVer, which uses both discordant mappings and read depth to predict copy number variants. In contrast to the simulated data set above, all known deletions analyzed here are larger than 1 kb and thus CNVer attains similar sensitivity to PR methods, like Hydra, GASV and Breakdancer. However, the number of discordant fragments per prediction, the criteria used to rank results for PR methods, provides a better trade off between true and false positive predictions than the estimated depth of coverage, which we use to rank CNVer predictions.

Even with the reduced coverage, compared to Pilot 2, the benefits of our probabilistic models are evident, and GASVPro outperforms all competing methods. GASVPro-HQ and GASVPro-Min2 have improved performance compared to Hydra, Hydra-HQ, Breakdancer and GASV. Note that the specificity for GASVPro drops below all other methods at the highest likelihood threshold (Figure 5c,d). This drop in performance is due to many predictions of GASVPro consisting of only a single discordant fragment mapping to a large region with very few concordant fragments. While it is possible these are true variants, it is more likely that most of them are false positives and, as such, eliminating these predictions (GASVPro-Min2) restores performance to that obtained by GASVPro-HQ. On this dataset, GASVPro-HQ correctly classifies 84 out of the 102 known deletions with highest likelihood as homozygous or heterozygous. As in the Pilot 2 data set, all 26 of 102 homozygous deletions were correctly classified, 3 of which have fewer than 3 supporting fragments.

We next evaluate the effect of increased coverage on each method by comparing the results from Pilot 2 (Figure 5a,b) with Pilot 1 (Figure 5c,d). For the methods utilizing only discordant mappings (Hydra, Hydra-HQ, GASV, and Breakdancer) performance is similar between Pilot 1 and Pilot 2 data. In contrast, performance of our probabilistic methods, GASVPro-HQ, GASVPro-Min2 and GASVPro, increases substantially with coverage. The maximum sensitivity of GASV Pro and GASVPro-HQ increases by about 20% on both data sets, from 97 to 119 and 96 to 114, respectively, for the fosmid validated set and 100 to 119 and 103 to 120 on the 1000 Genomes validated set. This improved performance results from integration of both discordant fragments (PR signal) and concordant fragments (RD signal). Increasing the sequencing coverage increases both discordant and concordant mappings throughout the genome. However, higher discordant coverage contributes to both true and false predictions, and thus methods that analyze only discordant fragments are less able to leverage the increased coverage to distinguish true from false predictions. In contrast, increased coverage by concordant fragments leads to sharper delineations between normal and deleted regions in the genome. Although it is possible that CNVer results would have also improved with the higher coverage data, a comparison was not possible as multiple libraries are not supported in the published CNVer implementation.

Finally, we remark on a practical difficulty in assessing the performance of methods on sequenced genomes. As indicated above, the complete set of SVs on these genomes is unknown. Thus, it is possible that predictions classified as 'novel predictions' could in fact be true, but yet unknown, variants. In addition, the set of validated variants that we use as true positives may not be representative of all SVs in these genomes. For example, we attained significant improvements in specificity for both inversions and deletions on NA12878 when we used a 'homozygous-only" model in GASVPro (Figure A8 in Additional file 1). This suggests that the set of known variants may underrepresent heterozygous deletions and inversions, which are presumably more difficult to detect and validate.

NA18507 deletions

We next compare all methods on previously published Illumina data [14] for the YRI individual NA18507. This genome was sequenced to high coverage (35 bp reads, ≈200 bp fragment length, 30× coverage) and, as for NA12878, there were two available validated sets of deletions and one set of inversions. In Figure 6, we show the results for previously validated fosmid deletions (Figure 6a) and validated deletions from the 1000 Genomes Project (Figure 6b). Since CNVer published their predictions on this data set, we compare directly to their previously reported results.

thumbnailFigure 6. An 'ROC curve' comparing the number of known deletions and novel deletion predictions for NA18507. (As for individual NA12878, we separately considered two sets of validated deletions [16,44].)

As above, employing our integrative probabilistic model for discordant fragments with unique mappings, GASVPro-HQ greatly improves performance compared to the original GASV. Using GASV alone, at maximum sensitivity we predict 55 of 93 deletions from the fosmid study with 2,240 novel predictions. In comparison, GASVPro-HQ successfully predicts the same 55 of 93 deletions with only 573 novel predictions. Similarly, for the 1000 Genomes deletions, at maximum sensitivity GASV predicts 95 of 118 deletions with 2,201 novel predictions while GASVPro-HQ attains the same sensitivity with only 1,372 novel predictions. Thus, using our probabilistic framework provides a two-fold increase in specificity at equal sensitivity. On the fosmid validated deletions, CNVer attains higher sensitivity than other methods and has overall higher specificity than GASV or Hydra at equal sensitivity (Figure 6a). However, this performance is not maintained on both sets of validated deletions (Figure 6b).

Overall, methods that analyze only unique mappings (Breakdancer, GASV, GASVPro-HQ, Hydra-HQ) outperformed those considering lower quality and ambiguous mappings. For this data set, including the full set of mappings (GASVPro and Hydra) greatly increases the number of predictions while, at best, modestly increasing the number of validated deletions that are correctly predicted. Indeed, running Hydra on only the unique mappings yields an 'ROC curve' similar to GASV alone. Although both GASVPro and original GASV match 70 of 93 variants from the fosmid study and 95 of 118 from 1000 Genomes Project, this is at the expense of predicting thousands of novel deletions on each data set, 5,535 and 21,523, respectively. We attain improved performance on the ambiguous data set by considering predictions with more than one supporting fragment, GASVPro-Min2; however, these results are still worse than GASV alone.

The decreased performance of GASVPro and Hydra on this data set, compared to NA12878 above, cannot be solely attributed to the read length as in both cases the sequenced reads were, on average, the same length, 37 bp. The differences seem likely due to difficulties in mapping uniquely to the reference. For NA12878, 31% of all mappings were unique while for NA18507, less than 1.5% of mappings were. In addition, there were more discordant fragments considered for NA18507, but fewer validated SVs. This combination may explain the substantial increase in 'novel' predictions, as compared to known deletions.

Inversions

In comparison to deletions, inversion SVs are more difficult to analyze for three reasons. First, there is no difference in read depth across the inversion, but only a change in read depth at the break ends (break end read depth). Second, there are few known inversion variants available for testing. Indeed, the 1000 Genomes SV paper [43] reports thousands of deletions but no inversions. Third, inversion SVs are known to have breakpoints with segmental duplications or other repetitive sequences, and aligning reads to these regions is complicated.

Even with these limitations we demonstrate the benefit of beRD in improving inversion prediction. As noted previously, on the simulated data set the beRD signal allowed GASVPro to correctly assign fragments to the true prediction when there were two choices possible. We now illustrate the beRD signal is beneficial on the real data. In Figure 7, we show the beRD for two inversions identified in NA18507 by GASVPro-HQ. As expected, in both cases there is a noticeable drop in coverage near the potential breakends, demonstrating the benefit of a model that utilizes beRD in addition to discordant fragments.

thumbnailFigure 7. Concordant coverage per position for two known inversions successfully predicted by GASVPro. (a) A prediction with 99 discordant fragments overlaps a chromosome 4 inversion with left breakend uncertainty of 89.040 to 89.069 Mb and right breakend uncertainty of 89.075 to 89.108 Mb. (b) A prediction with 15 discordant fragments overlaps a chromosome 6 inversion with left breakend uncertainty of 107.245 to 107.283 Mb and right breakend uncertainty of 107.277 to 107.315 Mb. For both predictions, a thick red line indicates the minimum and maximum mapped ends (x,y) for all supporting discordant fragments.

We compared predicted inversions for all methods to a set of validated inversions from a previous fosmid study [16] (see Materials and methods). The number of validated inversions is significantly smaller than the number of validated deletions; 23 inversions were validated in NA12878 and 10 in NA18507. All methods were far less sensitive in identifying inversions than deletions; maximum sensitivity over all methods was less than 20% on NA12878 and 70% on NA18507.

For all methods, we show the minimum number of inversion predictions needed to identify 1, 2 and 3 out of 23 inversions for NA12878 Pilot 1 and Pilot 2 data (Table 2). On Pilot 1 data our probabilistic models GASVPro and GASVPro-HQ attained improved sensitivity compared to GASV when detecting one and two inversions. In the case of the first inversion, the specificity increased by over 50% for GASVPro and over 80% for GASVPro-HQ. In almost all cases the higher coverage from Pilot 2 improved performance as the same number of inversions are detectable with fewer predictions. However, unlike for deletions, our probabilistic models do not always attain highest specificity. Over all methods, GASV was able to detect 2 inversions with the minimum number of predictions, while GASVPro-HQ detected 1 and 3 inversions with the minimum number of predictions. Finally, including lower quality mappings on this dataset did not yield improved performance; although GASVPro was able to attain highest sensitivity, detecting 4 of 23 inversions, this came at the price of thousands of more predictions.

Table 2. Inversion prediction in individual NA12878

Lastly, we analyze inversion results for NA18507 (Table 3). A total of two out of ten inversions are predicted from unique discordant mappings alone. All methods are able to predict these inversions, but Hydra-HQ is able to do so with only 43 predictions, the minimum number across all methods. As in the simulated Venter data, a third true inversion is detected with the inclusion of ambiguous mappings. In this case, GASVPro and GASVPro-Min2 detect three of ten inversions with 60% fewer predictions than Hydra. Thus, while the probabilistic model used by GASVPro is beneficial in some cases, unlike for deletion variants, it does not result in improved specificity for all cases.

Table 3. Inversion prediction in individual NA18507

Discussion

We introduce GASVPro, a method for SV detection that: (1) integrates both the RD signal (including the more localized beRD) and PR signal of structural variation into a single probabilistic model; (2) analyzes multiple possible read alignments using an MCMC procedure; and (3) explicitly defines uncertainty in the breakends of a variant. GASVPro is the first method to utilize a probabilistic formulation to identify generic SVs and not only copy number variants. We demonstrated that, compared to the previously published methods Breakdancer, Hydra and GASV, GASVPro has significantly higher specificity at equal or greater sensitivity in detecting known variants. Finally, our method is easily generalized to include additional signals predictive of variants.

The increased specificity and sensitivity of GASVPro demonstrates the benefit of integrating multiple signals of structural variation into a probabilistic model. In particular, read depth provides a strong signal to detect deletions and classify them as homozygous or heterozygous. As previously noted, GASVPro-HQ successfully classifies 104 of 119 deletions with known ploidy on NA12878. In contrast, methods that consider only discordant fragments, including Breakdancer, GASV and Hydra, yield more false positive predictions than GASVPro. In addition, we show that beRD is useful in increasing specificity for predicting copy-neutral inversions. Finally, our likelihood formulation provides more useful criteria for prioritizing predictions than the commonly used heuristic of the number of supporting fragments. We anticipate that including SRs will also aid in eliminating false positive predictions. In particular, the breakend polygon and beRD signal will suggest the sequence content of SRs. Thus, it will be possible to examine the data for SRs based on their sequence without exhaustive re-alignments to the reference.

The results of GASVPro demonstrate improved sensitivity when including reads with multiple possible alignments to the reference genome. However, this gain in sensitivity comes at a cost of reduced specificity as GASVPro makes many more predictions. On its surface, this is not too surprising as the inclusion of the additional lower quality alignments greatly increases the space of possible variants. The MCMC algorithm used in GASVPro is able to overcome the added ambiguity in part, with increased specificity over naïve inclusion of ambiguous alignments, but there remains a trade-off in improved sensitivity versus reduced specificity. An important caveat of this conclusion is that it is not possible to compute the actual specificity for the two sequenced human genomes, as the set of experimentally validated SVs is likely not to be the complete list of SVs in these genomes. In particular, the SVs with breakpoints in repetitive regions - those where we expect GASVPro to have some advantage - are also the hardest to predict and experimentally validate, and are thus likely greatly underrepresented in the list of experimentally validated predictions. As the lists of validated SVs become more complete, it will be possible to perform more complete benchmarking of the sensitivity and specificity of prediction methods.

The increased specificity attained by GASVPro demonstrates the benefit of including concordant coverage. An important consideration when using concordant mappings is that distinct regions of the genome will have reduced coverage for reasons unrelated to structural variation. As discussed in the Materials and methods section, repetitive sequences in the reference genome will reduce the ability of alignment software to align concordant fragments. In addition, as previously noted, there is a bias in Illumina sequencing related to the GC content of a region [14]. For the probabilistic model for deletions, we found that scaling concordant coverage according to the local mapability from the Rosetta Uniqueness Track improved sensitivity for detection. However, the use of a specific track is not essential for our model; indeed, the GASVPro code is modular and allows the user to substitute alternative models for concordant coverage and scaling. Finally, it has been previously suggested that RD is better modeled by distributions other than Poisson [50] and these could be used in place of the Poisson distribution in Equations 1 to 9.

The probabilistic method of GASVPro is formulated for a 'generic breakend' and is thus applicable to any SV class since we expect a drop in the coverage by concordant fragments at the breakends of the SV. Although deletion SVs have a stronger signal of decreased coverage throughout the region, by carefully considering the uncertainty in the location of mated breakends we identify the subtle signal of highly local drops in concordant coverage consistent with copy neutral variants such as inversions and reciprocal translocations. In this formulation, we assume 'clean' breaks in the genome, meaning there is no gain or loss of additional bases at the rearrangement junction. In practice, however, ambiguity in breakend location is likely to cause difficulties in estimating the true location and likelihood of a variant. For example, on the simulated Venter genome, coverage around the true variant breakends was significantly reduced by short indels.

As presented, our probabilistic model considered only concordant and discordant mappings; however, the model is easily generalized to include additional information about the alignments of PRs. As stated above, the SR signal can be included as part of the expected coverage around a breakend. The distribution of fragment lengths can be included when computing the likelihood of mated breakends (a,b) as each choice imposes a length on the supporting discordant fragments. Similarly, the mapping quality (or alignment score) of each mapped fragment can be incorporated into the probability function by considering the probability a chosen mapping is the correct one. We experimented with including quality scores on our simulated Illumina data set, but found this had a marginal effect on the results. However, with the addition of third-generation sequencing technologies with different error models [51], quality scores may be important.

Finally, because our probabilistic model is based on the generative processes of sequencing genomes, our model can be adapted to more general settings, such as detecting structural variation in cancer genomes. However, the extension to cancer genomes is non-trivial. In particular, to accurately analyze cancer genomes one would need to consider sample heterogeneity as the sequenced genomes are inevitably a mixture of normal and cancer genomes and possibly tumor subpopulations. In addition, our probabilistic model would need to incorporate aneuploidy by allowing more than two copies of the genomic region.

Conclusions

Structural variation - including duplications, deletions, insertions, inversions and translocations - is an important component of genetic variation in both human and cancer genomes. Current methods for SV detection typically consider only one of several signals from resequencing data when predicting structural variation. We introduced GASVPro, a probabilistic model for identification of structural variation integrating both RD and PR signals of SVs. Compared to existing methods, GASVPro has high sensitivity in predicting known variants while reducing the number of false positives by up to 90% for deletions and 50% for inversions.

Materials and methods

Defining breakpoint regions with GASV

GASVPro clusters discordant PRs using the previously published program GASV [33]. The GASV algorithm explicitly represents uncertainty in the location of the endpoints of the SV, the mated breakends, by a polygon and clusters discordantly mapped fragments by utilizing a computational geometric approach for intersecting polygons. We briefly overview the approach used in GASV; for a more detailed discussion of the GASV algorithm, refer to [33].

A discordant mapping indicates a SV in the test genome defined by a novel adjacency (a,b), where positions a and b are adjacent in the test genome, but not in the reference genome (Figure 1). A single fragment alone does not uniquely specify the pair of breakends (a,b) defining the rearrangement, but rather defines uncertainty in the location of the breakends. Formally, if we assume that a discordant fragment corresponds to exactly one SV, then the mapped locations, x and y, of the fragment endpoints (without loss of generality we restrict x < y), and the breakends a and b satisfy:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M113">View MathML</a>, (11)

where sign(x) and sign(y) are 1 if the reads align to the positive strand and have convergent orientation and -1 otherwise. Here we assume convergent orientation is when reads have opposite orientation with the left read forward and the right read reversed as in the case for Illumina sequencing technology. The inequality (Equation 11) defines a trapezoid in the plane; discordant fragments corresponding to the same SV will have overlapping trapezoids and their intersection can be used to further refine the uncertainty in breakend location as in Figure 1b.

Concordant coverage and mapability

We consider concordant mappings when computing the likelihood of a variant because statistically significant changes in coverage indicate the presence of rearrangements relative to the reference genome. However, in addition to SVs, several local factors will affect coverage by concordant fragments.

Reads originating from duplications present in both the test and reference genome cannot be mapped to a unique position. Thus, such regions will have low coverage due to restrictions in local mapability. To adjust for variable mapability throughout, in the deletion model we scaled the number of concordantly mapped fragments using The Rosetta Uniqueness Track. The Rosetta Uniqueness Track, created by John Castle at Rosetta Inpharmatics (Merck; UCSC Genome Browser), quantifies mapability by considering a 35-bp tiling of the genome and determining which 35-mers will have a unique mapping to the reference genome with the Burrows-Wheeler aligner (BWA) mapping tool.

For an interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M114">View MathML</a>, let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M115">View MathML</a> be the fraction of uniquely mapable bases in <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M114">View MathML</a>according to the Rosetta Uniqueness Track and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M116">View MathML</a> be the number of observed concordant fragments whose mappings overlap <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M114">View MathML</a>. In our analysis we consider the scaled concordant coverage <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M117">View MathML</a>, where:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M118">View MathML</a>

(12)

where we use <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M119">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M120">View MathML</a>. Notice, when the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M114">View MathML</a> does not have compromised mapability, that is, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M121">View MathML</a>, we do not adjust the number of observed fragments, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M122">View MathML</a>.

Note that in our analysis we do not scale the number of discordant fragments. In practice we found an abundance of discordant fragments mapping to regions of very low-mapability and scaling the number of discordant fragments led to an abundance of false positive predictions. Finally, we utilized a heuristic when computing the likelihood of SVs. If the concordant coverage for a breakpoint or interval was in the top 0.01% according to the Poisson model, we automatically assigned <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M123">View MathML</a>. Since under the Poisson model extremely high coverage by concordant fragments occurs with low probability, this threshold further restricts the region considered to represent SV endpoints. In such cases, we expect coverage by concordant fragments to be decreased compared to the rest of the genome.

Prediction uncertainty and the double uncertainty metric

Most studies determine if predictions match a known variant by overlapping a predicted genomic interval with the interval reported for the known variant. However, the criteria for 'overlap' differs among methods. For example, Chen et al. [32] considered a match when the intersection of the intervals is at least 50% of the union of the two or if the predicted interval entirely contains the known variant. While Hormozdiari F et al. [42] reported a deletion as matching a known variant if they had 50% reciprocal overlap and considered any overlap between an inversion and known variant. Although these criteria do eliminate some types of spurious identification, the inherent weakness of these metrics is that they do not unambiguously represent the underlying uncertainty in the predicted or reported variants.

We introduce a criteria for overlap, the 'double uncertainty' metric, that explicitly represents uncertainty in both the coordinates of known variants, reference uncertainty, and predictions, prediction uncertainty. We say a prediction and known variant overlap if the pairs of intervals specifying uncertainty in their coordinates do. Formally, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M277','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M277">View MathML</a> specifies the prediction uncertainty and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M124">View MathML</a> is the reference uncertainty. That is, for the predicted SV, the left breakend is predicted to lie in the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M278','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M278">View MathML</a> and the right breakend in the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M279','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M279">View MathML</a>; similarly, the reported known variant has left breakend in the interval, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M125">View MathML</a> and right breakend in the interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M126">View MathML</a>. A predicted SV overlaps a known variant in the double uncertainty metric if both of the following are satisfied:

1. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M275','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M275">View MathML</a>

2. <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M276','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M276">View MathML</a>

We provide illustrations of the double uncertainty metric in Additional file 1. We illustrate the conversion from output formats from different SV programs to use in the comparison in Figure A4 and overlap in the double uncertainty metric in Figure A5 in Additional file 1.

In practice, the reference uncertainty, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M127">View MathML</a>, and prediction uncertainty, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M280','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M280">View MathML</a>, reflect limitations on the technology used, such as fragment size, but may also include ambiguity inherent in a breakend within a repetitive region. We use prediction uncertainty <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M281','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M281">View MathML</a> to reflect the sequencing process. We base the reference uncertainty on the specific data set and technology used to obtain the known variants. For the Venter simulated deletions, reference uncertainty is 0 because these variants are specified to the breakpoint. For variants from fosmid mappings of NA12878 or NA18507 we use fosmid mappings reported by Kidd et al. [16] to determine the breakend polygon with GASV, and use the uncertainty directly from these polygons.

Markov chain Monte Carlo procedure

Given an alignment matrix A, we define a Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M128">View MathML</a> over the space of mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> that has <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M129">View MathML</a> as its stationary distribution. We use the Metropolis Hastings algorithm to define transition probabilities between matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M130">View MathML</a>, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M131">View MathML</a>. The probability of transitioning between states depends on two terms: proposing a move with proposal distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M132">View MathML</a> and accepting this move with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M133">View MathML</a>. That is:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M134">View MathML</a>

If the proposal distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M135">View MathML</a> yields an irreducible and aperiodic Markov chain, then using the acceptance probability of the Metropolis Hastings procedure:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M136">View MathML</a>

(13)

results in convergence of <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M128">View MathML</a> to the stationary distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M137">View MathML</a>. The first step in our MCMC procedure (Figure A2 in Additional file 1) is to stay at the same mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> with probability 1/2. This self-edge guarantees aperiodicity, but irreducibility depends on the set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M138">View MathML</a> of possible moves. We developed several classes of moves (Figure A3 in Additional file 1) to explore the space of mapping matrices that yield irreducibility. The first move consists of naively moving a fragment from one mapping to another:

Naive (N):

Select a row i with uniform probability:

If there is a j such that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M139">View MathML</a> set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M140">View MathML</a>. If there exists k j such that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M141">View MathML</a>, then with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M142">View MathML</a> select a k uniformly and set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M143">View MathML</a>. Otherwise, leave <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M144">View MathML</a> for all k.

If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M145">View MathML</a> for all j, with uniform probability select a j where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M146">View MathML</a> and set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M147">View MathML</a>.

Notice that the Naive (N) move always changes the mapping matrix. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M148">View MathML</a> consists of only class N moves, then the chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M149">View MathML</a> satisfies irreducibility because any two mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M150">View MathML</a> may be reached from one another by a series of class N moves. Thus, the Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M151">View MathML</a> with <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M148">View MathML</a> equal to the all class N moves will yield the stationary distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M152">View MathML</a>. However, we found empirically that the mixing time of a Markov chain with only a class N move was long (Section A2 in Additional file 1). Thus, we define three additional moves, which empirically yielded improved mixing times. (Recall from the main text that, for an assignment matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M153">View MathML</a> and associated mapping matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a>, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M154">View MathML</a> is the number of SVs with positive support, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M155">View MathML</a> is the set of rows in <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M153">View MathML</a> with a 1 in the column j and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M156">View MathML</a> is the total support for a variant j.)

Remove a single column (Z): this move zeroes out a column of M:

With probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M157">View MathML</a>, select a non-zero column j.

For all <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M158">View MathML</a>:

If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M159">View MathML</a>, set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M160">View MathML</a>. If there exists k j such that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M161">View MathML</a>, with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M162">View MathML</a> uniformly select a column k and set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M163">View MathML</a>. Otherwise, leave <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M164">View MathML</a> for all k.

Revive a zero column (<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M165">View MathML</a>): This move adds support to a zero column of A:

With probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M166','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M166">View MathML</a>, where n is the total number of variants in V, select a zero column j, that is, a column j with <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M167','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M167">View MathML</a>.

While <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M168','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M168">View MathML</a> for all <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M169','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M169">View MathML</a>:

For each i, with probability 1/2, set <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M170','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M170">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M171','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M171">View MathML</a> for all k j.

Swap columns (S): this move swaps some entries of two columns of A:

Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M172','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M172">View MathML</a>. With probability:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M173">View MathML</a>

select a pair of columns <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M174">View MathML</a> conditional on at least one column having non-zero entries.

For all <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M175','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M175">View MathML</a>:

If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M176','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M176">View MathML</a> or <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M177">View MathML</a>, then with probability 1/2, swap <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M178">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M179">View MathML</a>.

Repeat if necessary to ensure at least one entry is swapped between columns j and k.

The last step in formalizing the Markov chain is to compute the acceptance probabilities. As described above, the acceptance probability depends on the proposal distribution and the probability of the mapping matrix. In fact, since the acceptance probability depends on only the ratio <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M180">View MathML</a>, the computation is simplified to considering only the columns (variants) and rows (fragments) that differ between the matrices. This ratio is simple for class N and S moves since a Naive move alters exactly one row and at most two columns and a Swap move alters exactly two columns. Although in the worst case Z and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M181">View MathML</a> may alter every row and column of the mapping matrix, this is quite rare in practice.

In order to compute the proposal distribution, we need to consider all ways to transition between mapping matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M182">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a>. First, note that all move classes result in a new matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M183">View MathML</a>. Thus, the probability of a self-loop is always fixed at 1/2. Second, note that in many cases different move types will create the same resulting mapping matrix. For example, a class Z move on a variant with only a single supporting fragment is the same as a class N move on that supporting fragment. Thus, the proposal distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M184">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M185">View MathML</a> must consider all possible move types. We use <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M186">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M187">View MathML</a> to distinguish between the proposal distribution conditional on a move class.

A class N move alters the assignment of exactly one row. Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M188','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M188">View MathML</a> be the number of rows (that is, discordant fragments), then probability of proposing <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M189">View MathML</a> with a class N move will be one of the following values:

1. If the altered row had only one possible non-zero entry in A, that is <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M190">View MathML</a>, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M191">View MathML</a>,

2. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M192">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M193">View MathML</a> for <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M194">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M195','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M195">View MathML</a>, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M196','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M196">View MathML</a>,

3. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M197','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M197">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M198','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M198">View MathML</a> for <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M199','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M199">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M200','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M200">View MathML</a> for all k, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M201','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M201">View MathML</a>,

4. If <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M202','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M202">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M203','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M203">View MathML</a> for <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M204','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M204">View MathML</a> for all i and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M205','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M205">View MathML</a>, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M206','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M206">View MathML</a>

and 0 if no class N move is possible.

A class Z move results in a single empty variant. Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M207','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M207">View MathML</a> be the number of non-empty columns. The proposal distribution of a class Z move depends on selecting the column, with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M208','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M208">View MathML</a> and reassigning the rows to either errors, with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M209','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M209">View MathML</a>, or another mapping, with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M210','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M210">View MathML</a>. Let x be the number of rows moved to an error, when another mapping is possible, and y be the set of rows moved to another mapping given that at least two mappings are possible, then:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M211','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M211">View MathML</a>

(14)

and 0 if no class Z move is possible.

In a class <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M212','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M212">View MathML</a> move, all altered rows are moved to the same originally empty column. A class <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M213','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M213">View MathML</a> move depends on selecting an empty column to add to, with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M214','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M214">View MathML</a>, and moving entries from other columns. Let j be the column that was selected to be added to, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M215','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M215">View MathML</a> is the total number of rows that could be assigned to j. We first select the number of entries k to move to column j, conditional on at least one entry changing. Then, the proposal distribution is given by:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M216','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M216">View MathML</a>

(15)

and 0 if no class <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M217','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M217">View MathML</a> move is possible.

The proposal distribution for a class S move is nearly identical to the class <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M218','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M218">View MathML</a> move, except we need only consider the probability of picking the two columns instead of picking a single non-empty column. As before we define <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M219','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M219">View MathML</a>if no class S move is possible.

Finally, for the full proposal distribution:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M220','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M220">View MathML</a>

(16)

where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M221','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M221">View MathML</a> is an appropriate weighting factor based on which moves are possible. For example, if the transition from <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M222','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M222">View MathML</a> is possible with all move types, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M223','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M223">View MathML</a>.

We now formally demonstrate our Markov chain converged to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M224','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M224">View MathML</a> given in Equation 10. As described above, our chain is aperiodic and irreducible, since there is a nonzero probability of moving from any one state to any other state in a finite number of steps. A finite state, irreducible and aperiodic Markov chain has a unique stationary distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M225','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M225">View MathML</a> and this distribution satisfies the detailed balance condition:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M226','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M226">View MathML</a>

(17)

Here, transition probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M227','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M227">View MathML</a> depends on two terms, proposing a move from state <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M228','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M228">View MathML</a> with proposal distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M229','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M229">View MathML</a> and accepting this move with probability <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M230','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M230">View MathML</a>: <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M231','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M231">View MathML</a>. We show that the acceptance probability satisfies the detailed balance condition in Equation 17. Without loss of generality assume <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M232','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M232">View MathML</a>, then <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M233','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M233">View MathML</a>. Thus:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M234','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M234">View MathML</a>

Efficient sampling of mapping matrices

A practical difficulty in sampling from the space of mapping matrices is the high dimension of the sampling space with millions of discordant fragments and hundreds of thousands of potential variants in the genomes in this study. However, we are still able to efficiently explore the space of mapping matrices by subdividing potential variants and discordant fragments into independent subsets and sampling instead over sub-matrices of <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M76">View MathML</a> (Figure 3).

Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M235','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M235">View MathML</a> be a bi-partite graph defined by disjoint sets of vertices corresponding to the fragments, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M236','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M236">View MathML</a>, and variants <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M237','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M237">View MathML</a>. There is an edge from a vertex <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M238','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M238">View MathML</a> to <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M239','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M239">View MathML</a>if there is a mapping of f that supports the SV <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M4">View MathML</a>. A connected component c of G corresponds to a sub-matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M240','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M240">View MathML</a> of A and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M241','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M241">View MathML</a> of M. The moves employed in our MCMC procedure only modify assignments belonging to a single connected component of G. Further, since:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M242','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M242">View MathML</a>

(18)

we subdivide our sampling by separately considering each connected component in G (Figure 3). Sampling separately over mapping sub-matrices <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M243','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M243">View MathML</a> for each c and combining results is equivalent to sampling over the full space of mapping matrices because each move in the former has an equivalent move with equal probability in the latter and vice versa. Further, because we never compute P(M|A) alone, but only the ratio P(M'|A)/P(M|A) for a proposed mapping matrix M', Equation 18 is more general than needed. Thus, we instead verify the following sufficient condition:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M244','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M244">View MathML</a>

(19)

As stated above, each move only affects one connected component. Let <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M245','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M245">View MathML</a> be the component affected by the move, then the ratio on the left hand side of Equation 19 becomes <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M246','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M246">View MathML</a>, since c' is the only component changed. Thus, we replace the left hand side in Equation 19:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M247','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M247">View MathML</a>

(20)

To see that Equation 20 holds as equality, recall that P(M'|A)/P(M|A) is computed over rows and columns of M and M' except the term <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M248','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M248">View MathML</a>, which only depends on the total number of variants with positive support. Again, let c' be the component affected by the move. Thus, when computing <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M249','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M249">View MathML</a>, every term corresponding to rows or columns that belong to components other than c' are cancelled. Moreover the ratio <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M250','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M250">View MathML</a> depends on only the number of columns whose support changes. Thus, this ratio also depends on only the columns affected by the move. Therefore, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M251','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M251">View MathML</a> also becomes <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M252','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M252">View MathML</a> and Equation 20 is satisfied.

Defining the predicted variants

As indicated in the main text, we considered several different procedures for reporting a final set of predictions from the mapping matrices M sampled during the MCMC procedure. The simplest method is to consider a single mapping matrix that maximizes P(M|A) as the truth and report the resulting variants. However, we found a useful procedure was to consider the entire set of mapping matrices sampled during the Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M253">View MathML</a>.

We first consider a variant-based method for analyzing the Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M253">View MathML</a>. We note that the likelihood ratio, Λ, was a useful test statistic to prioritize variants when the set of mappings was fixed. We generalize <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M254','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M254">View MathML</a> to be the likelihood ratio of a variant according to a specified mapping matrix and seek the likelihood of a variant over the entire space of mapping matrices:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M255','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M255">View MathML</a>

(21)

Assuming the Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M253">View MathML</a> has converged, we can approximate Λ(V) from the chain:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M256','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M256">View MathML</a>

(22)

We also analyzed a fragment-based approach by considering each fragment independently over each mapping matrix M sampled in the Markov chain <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M253">View MathML</a>. For each fragment i and mapping j we define the average support for this mapping as:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M257','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M257">View MathML</a>

(23)

(Note that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M258','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M258">View MathML</a> is directly determined during the MCMC sampling procedure.) If a fragment has the same assigned mapping for a majority of the Markov chain (that is, <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M259','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M259">View MathML</a>), we are inclined to label that alignment the 'true mapping'. That is, we define a matrix <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M260','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M260">View MathML</a> where:

<a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M261','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M261">View MathML</a>

Notice that <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M262','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M262">View MathML</a> has two favorable properties: we consider at most one mapping for each fragment, and we exclude fragments that do not strongly support a single SV. In the results we present we define our final set of predictions by <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M263','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M263">View MathML</a> and report variants based on their likelihood ratio Λ according to this mapping matrix. However, over all datasets studied, we found only minor differences in the ROC curves for three different sets of predictions (see Figure A4 in Additional file 1 for a comparison).

Mapping reads

We analyzed alignments to two human genomes (NA18507 and NA12878) and a simulated human chromosome. In all cases, we used two sets of alignment data: a high quality data set and a low quality data set. The high quality data set consisted of fragments with a clear and unique mapping to the reference genome. For human genomes NA18507 and NA12878, the reported mappings (from [14] and [44], respectively), were taken as the high-quality set. For the simulated data for Venter chromosome 17, we mapped reads to the reference chromosome 17 with BWA [52] to determine the high quality unique mappings.

The low quality alignments were obtained by using NovaAlign [48] to realign reads not belonging to a uniquely mapped pair. We allowed up to 100 alignments per read, but to eliminate fragments from highly repetitive data, we removed all fragments with more than 100 alignments genome-wide. Although our low quality alignments contained ambiguous fragments, many were low quality unique mappings. For NA18507, 516,941 out of 888,868 fragments included in the low quality set had unique mappings. For NA12878, 69,388 out of 157,842 fragments had unique mappings. For both sets of alignments, we removed concordant fragments, and retained all alignments with mapped distance ≤500 kb and with mapping quality >10.

For Breakdancer and GASV, results were only given on the high quality mappings. For GASVPro and Hydra, the suffix '-HQ' specifies results on the high quality datasets; results without the suffix were on the combined high and low quality datasets.

Running GASVPro

Runtime analysis

We now discuss details of the GASVPro algorithm; after identifying the set of discordant and concordant mappings, there are three steps in the pipeline of GASVPro: (1) clustering discordant mappings with GASV (O(nlogn) in the number of discordant fragments); (2) determining concordant coverage over each breakend polygon, (O(ClogC) where C the number of concordant fragments); and (3) running the MCMC sampling procedure.

When running the MCMC procedure on each connected component (Figure 3), we utilize a fixed number of burn-in iterations (105) and sampling steps (9 × 105) based on heuristics developed in analyzing the simulated data. The complexity of the MCMC depends on selecting a move and deciding whether to accept the proposed move, each of which depends on the size of the connected component considered. With m discordant fragments and n variants in a connected component, the time to select a move, over all possible move types, is <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M264','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M264">View MathML</a>. Determining if a move is accepted depends on the number of altered variants and fragments; in the worst case all variants and fragments could be altered O(n+m), but in practice the total number of modified cases is quite small.

MCMC parameters and considerations

The parameter λ varied with the coverage of the data; we used λ = 0.3 for the simulated Venter chromosome and NA12878, and λ = 0.6 for NA18507. Our final results were not sensitive to the exponential prior on the number of variants. However, this term may be useful in other analyses. As discussed in Additional file 1, when η is large, P(M|A) is dominated by the exponential distribution <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M265','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M265">View MathML</a>, which is maximized when the number of variants is minimized. In addition, for the genomes we studied we further restricted the space of mapping matrices by fixing the mapping for fragments with a unique assignment in the genome. As such, the MCMC procedure would transition between possible mappings for only truly fragments with multiple possible alignments. Such a heuristic greatly reduces the computation time of the MCMC by significantly reducing the total space to sample.

Finally, additional considerations were made in the analysis of NA18507. A combination of high coverage and short reads (37 bp) resulted in nearly half a million predicted deletions and several extremely large connected components ≥2 × 105 clusters with over 106 fragments. Because of computational difficulties in analyzing these clusters, along with difficulties in determining convergence of the MCMC procedure, we eliminated all mappings to the centromeres and retained only mappings that indicated a deletion larger than 1,000 bp. (In the results discussed in the main text, all methods were compared on this same reduced set of fragments.) After these measures, there remained six connected components where the number of edges in the graph exceeded 106. In analyzing these connected components, we simply assigned fragments with unique mappings.

Pruning predicted structural variants

Results from all methods were pruned in a post-processing step to eliminate redundant predictions. First, predictions from all methods were converted to intervals. For GASV, a breakend polygon B was converted into an interval <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M266','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M266">View MathML</a>, where <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M267','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M267">View MathML</a> and <a onClick="popup('http://genomebiology.com/2012/13/3/R22/mathml/M268','MathML',630,470);return false;" target="_blank" href="http://genomebiology.com/2012/13/3/R22/mathml/M268">View MathML</a>. For Breakdancer we considered the reported interval [x,y] and for Hydra we considered the interval [IE,OS] (Figure A5 in Additional file 1).

Two predictions were said to be redundant if the intersection of their intervals was at least 50% of the union or if one interval contained the other. In such cases, for GASV, Breakdancer and Hydra, the prediction with more supporting fragments was retained. For GASVPro, the prediction with greater likelihood according to the respective model was retained.

Known variants

As discussed in the text, we compared predictions to sets of known SVs with the double uncertainty metric. Importantly, this metric considers uncertainty in the location of both the prediction and known variant.

For the simulated Venter genome, we compare predictions to the set of deletions and inversions detailed in [47]; there were 4 inversions and we used the 124 deletions with length ≥125 bp. When comparing predictions to known variants, we use reference uncertainty δ = 0 because the true location of the breakpoints is known exactly.

For both genomes, NA12878 and NA18507, we compared predictions from each method to two sets of validated variants. The first was from a fosmid sequencing study [16] and the second from the 1000 Genomes Project pilot study [44]. Although the combined set of variants likely contained duplicates, to maximize sensitivity we did not attempt to reduce these sets by eliminating predictions reported by both studies.

A fosmid sequencing study validated hundreds of inversions and deletions [16]. We considered only the subset of predictions that were validated in the same individuals (NA18507, NA12878). As previously reported, several of the predictions from the original study did not have a common breakpoint region defined by fosmid mappings [33]. Thus, we restricted the validated set to the 93 deletions and 10 inversions for NA18507 and 151 deletions and 23 inversions for NA12878 that corresponded to clusters of at least two fosmids. In comparisons, we utilized the inherent uncertainty in breakend polygons [33] as the reference uncertainty.

The 1000 Genomes Project pilot study reported validated deletion variants as well as the individuals to whom they belonged [44]. (Note that the pilot study did not report inversion SVs.) We separated validated variants that were identified by PR mapping and restricted to deletions that were larger than 5 kb. The final set represented a total of 118 deletions for NA18507 and 139 deletions for NA12878. Because many next-generation sequencing libraries were used in predicting these variants, we used δ = 200 as an approximation for the prediction uncertainty in these variants.

Abbreviations

beRD: breakend read depth; bp: base pair; BWA: Burrows-Wheeler aligner; GASV: Geometric Analysis of Structural Variation; MCMC: Markov chain Monte Carlo; PR: paired read; RD: read depth; ROC: receiver operating characteristic; SR: split read; SV structural variant.

Competing interests

The authors declare that they have no competing interests.

Authors' contributions

SS, SO and BJR conceived and designed the method. SS, SO, LP and HW developed code and generated datasets. SS, BJR, LP and SO performed the analyses. SS and BJR wrote the manuscript. All authors read and approved the final manuscript.

Acknowledgements

We would like to thank Paul Medvedev for his assistance with running CNVer and Anna Ritz for helpful discussions regarding the manuscript. This work is supported by National Institutes of Health (R01 HG5690) and Burroughs Wellcome Career Award at the Scientific Interface to BJR. Some read alignments were obtained using the free version of Novoalign [48].

References

  1. Conrad DF, Pinto D, Redon R, Feuk L, Gokcumen O, Zhang Y, Aerts J, Andrews TD, Barnes C, Campbell P, Fitzgerald T, Hu M, Ihm CH, Kristiansson K, Macarthur DG, Macdonald JR, Onyiah I, Pang AW, Robson S, Stirrups K, Valsesia A, Walter K, Wei J, Wellcome Trust Case Control Consortium, Tyler-Smith C, Carter NP, Lee C, Scherer SW, Hurles ME: Origins and functional impact of copy number variation in the human genome.

    Nature 2009, 464:704-712. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  2. Xing J, Zhang Y, Han K, Salem AH, Sen SK, Huff CD, Zhou Q, Kirkness EF, Levy S, Batzer MA, Jorde LB: Mobile elements create structural variation: analysis of a complete human genome.

    Genome Res 2009, 19:1516-1526. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  3. Navin N, Krasnitz A, Rodgers L, Cook K, Meth J, Kendall J, Riggs M, Eberling Y, Troge J, Grubor V, Levy D, Lundin P, Månér S, Zetterberg A, Hicks J, Wigler M: Inferring tumor progression from genomic heterogeneity.

    Genome Res 2010, 20:68. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  4. Ding L, Ellis MJ, Li S, Larson DE, Chen K, Wallis JW, Harris CC, McLellan MD, Fulton RS, Fulton LL, Abbott RM, Hoog J, Dooling DJ, Koboldt DC, Schmidt H, Kalicki J, Zhang Q, Chen L, Lin L, Wendl MC, McMichael JF, Magrini VJ, Cook L, McGrath SD, Vickery TL, Appelbaum E, Deschryver K, Davies S, Guintoli T, Lin L, et al.: Genome remodelling in a basal-like breast cancer metastasis and xenograft.

    Nature 2010, 464:999-1005. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  5. Pleasance ED, Cheetham RK, Stephens PJ, McBride DJ, Humphray SJ, Greenman CD, Varela I, Lin ML, Ordóñez GR, Bignell GR, Ye K, Alipaz J, Bauer MJ, Beare D, Butler A, Carter RJ, Chen L, Cox AJ, Edkins S, Kokko-Gonzales PI, Gormley NA, Grocock RJ, Haudenschild CD, Hims MM, James T, Jia M, Kingsbury Z, Leroy C, Marshall J, Menzies A, et al.: A comprehensive catalogue of somatic mutations from a human cancer genome.

    Nature 2009, 463:191-196. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  6. Ding L, Wendl M, Koboldt D, Mardis E: Analysis of next-generation genomic data in cancer: accomplishments and challenges.

    Hum Mol Genet 2010, 19:R188. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  7. Wittler R, Chauve C: Consistency-based detection of potential tumor-specific deletions in matched normal/tumor genomes.

    BMC Bioinformatics 2011, 12:S21. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  8. Carreto L, Eiriz M, Gomes A, Pereira P, Schuller D, Santos M: Comparative genomics of wild type yeast strains unveils important genome diversity.

    BMC Genomics 2008, 9:524. PubMed Abstract | BioMed Central Full Text | PubMed Central Full Text OpenURL

  9. Cridland J, Thornton K: Validation of rearrangement break points identified by paired-end sequencing in natural populations of Drosophila melanogaster.

    Genome Biol Evol 2010, 2:83. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  10. Yalcin B, Wong K, Agam A, Goodson M, Keane TM, Gan X, Nellåker C, Goodstadt L, Nicod J, Bhomra A, Hernandez-Pliego P, Whitley H, Cleak J, Dutton R, Janowitz D, Mott R, Adams DJ, Flint J: Sequence-based characterization of structural variation in the mouse genome.

    Nature 2011, 477:326-329. PubMed Abstract | Publisher Full Text OpenURL

  11. Medvedev P, Stanciu M, Brudno M: Computational methods for discovering structural variation with next-generation sequencing.

    Nat Methods 2009, 6:S13-S20. PubMed Abstract | Publisher Full Text OpenURL

  12. Alkan C, Coe B, Eichler E: Genome structural variation discovery and genotyping.

    Nat Rev Genet 2011, 12:363-376. PubMed Abstract | Publisher Full Text OpenURL

  13. Dalca A, Brudno M: Genome variation discovery with high-throughput sequencing data.

    Brief Bioinformatics 2010, 11:3. PubMed Abstract | Publisher Full Text OpenURL

  14. Bentley DR, Balasubramanian S, Swerdlow HP, Smith GP, Milton J, Brown CG, Hall KP, Evers DJ, Barnes CL, Bignell HR, Boutell JM, Bryant J, Carter RJ, Keira Cheetham R, Cox AJ, Ellis DJ, Flatbush MR, Gormley NA, Humphray SJ, Irving LJ, Karbelashvili MS, Kirk SM, Li H, Liu X, Maisinger KS, Murray LJ, Obradovic B, Ost T, Parkinson ML, Pratt MR, et al.: Accurate whole human genome sequencing using reversible terminator chemistry.

    Nature 2008, 456:53-59. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  15. Sudmant P, Kitzman J, Antonacci F, Alkan C, Malig M, Tsalenko A, Sampas N, Bruhn L, Shendure J, Eichler E: Diversity of human copy number variation and multicopy genes.

    Science 2010, 330:641. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  16. Kidd JM, Cooper GM, Donahue WF, Hayden HS, Sampas N, Graves T, Hansen N, Teague B, Alkan C, Antonacci F, Haugen E, Zerr T, Yamada NA, Tsang P, Newman TL, Tuzun E, Cheng Z, Ebling HM, Tusneem N, David R, Gillett W, Phelps KA, Weaver M, Saranga D, Brand A, Tao W, Gustafson E, McKernan K, Chen L, Malig M, et al.: Mapping and sequencing of structural variation from eight human genomes.

    Nature 2008, 453:56-64. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  17. Korbel JO, Urban AE, Affourtit JP, Godwin B, Grubert F, Simons JF, Kim PM, Palejev D, Carriero NJ, Du L, Taillon BE, Chen Z, Tanzer A, Saunders ACE, Chi J, Yang F, Carter NP, Hurles ME, Weissman SM, Harkins TT, Gerstein MB, Egholm M, Snyder M: Paired-end mapping reveals extensive structural variation in the human genome.

    Science 2007, 318:420-426. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  18. Iafrate A, Feuk L, Rivera M, Listewnik M, Donahoe P, Qi Y, Scherer S, Lee C: Detection of large-scale variation in the human genome.

    Nat Genet 2004, 36:949-951. PubMed Abstract | Publisher Full Text OpenURL

  19. Tuzun E, Sharp AJ, Bailey JA, Kaul R, Morrison VA, Pertz LM, Haugen E, Hayden H, Albertson D, Pinkel D, Olson MV, Eichler EE: Fine-scale structural variation of the human genome.

    Nat Genet 2005, 37:727-732. PubMed Abstract | Publisher Full Text OpenURL

  20. Sebat J, Lakshmi B, Troge J, Alexander J, Young J, Lundin P, Månér S, Massa H, Walker M, Chi M, Navin N, Lucito R, Healy J, Hicks J, Ye K, Reiner A, Gilliam TC, Trask B, Patterson N, Zetterberg A, Wigler M: Large-scale copy number polymorphism in the human genome.

    Science 2004, 305:525-528. PubMed Abstract | Publisher Full Text OpenURL

  21. Abel H, Duncavage E, Becker N, Armstrong J, Magrini V, Pfeifer J: SLOPE: a quick and accurate method for locating non-SNP structural variation from targeted next-generation sequence data.

    Bioinformatics 2010, 26:2684. PubMed Abstract | Publisher Full Text OpenURL

  22. Volik S, Zhao S, Chin K, Brebner JH, Herndon DR, Tao Q, Kowbel D, Huang G, Lapuk A, Kuo WL, Magrane G, De Jong P, Gray JW, Collins C: End-sequence profiling: sequence-based analysis of aberrant genomes.

    Proc Natl Acad Sci USA 2003, 100:7696-7701. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  23. Hillmer AM, Yao F, Inaki K, Lee WH, Ariyaratne PN, Teo AS, Woo XY, Zhang Z, Zhao H, Ukil L, Chen JP, Zhu F, So JB, Salto-Tellez M, Poh WT, Zawack KF, Nagarajan N, Gao S, Li G, Kumar V, Lim HP, Sia YY, Chan CS, Leong ST, Neo SC, Choi PS, Thoreau H, Tan PB, Shahab A, Ruan X, et al.: Comprehensive long-span paired-end-tag mapping reveals characteristic patterns of structural variations in epithelial cancer genomes.

    Genome Res 2011, 21:665. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  24. Alkan C, Sajjadian S, Eichler EE: Limitations of next-generation genome sequence assembly.

    Nat Methods 2011, 8:61-65. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  25. Schatz MC, Delcher AL, Salzberg SL: Assembly of large genomes using second-generation sequencing.

    Genome Res 2010, 20:1165-1173. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  26. Yoon S, Xuan Z, Makarov V, Ye K, Sebat J: Sensitive and accurate detection of copy number variants using read depth of coverage.

    Genome Res 2009, 19:1586-1592. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  27. Chiang DY, Getz G, Jaffe DB, O'Kelly MJ, Zhao X, Carter SL, Russ C, Nusbaum C, Meyerson M, Lander ES: High-resolution mapping of copy-number alterations with massively parallel sequencing.

    Nat Methods 2009, 6:99-103. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  28. McKernan KJ, Peckham HE, Costa GL, McLaughlin SF, Fu Y, Tsung EF, Clouser CR, Duncan C, Ichikawa JK, Lee CC, Zhang Z, Ranade SS, Dimalanta ET, Hyland FC, Sokolsky TD, Zhang L, Sheridan A, Fu H, Hendrickson CL, Li B, Kotler L, Stuart JR, Malek JA, Manning JM, Antipova AA, Perez DS, Moore MP, Hayashibara KC, Lyons MR, Beaudoin RE, et al.: Sequence and structural variation in a human genome uncovered by short-read, massively parallel ligation sequencing using two-base encoding.

    Genome Res 2009, 19:1527-1541. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  29. Xie C, Tammi MT: CNV-seq, a new method to detect copy number variation using high-throughput sequencing.

    BMC Bioinformatics 2009, 10:80. PubMed Abstract | BioMed Central Full Text | PubMed Central Full Text OpenURL

  30. Nord A, Lee M, King M, Walsh T: Accurate and exact CNV identification from targeted high-throughput sequence data.

    BMC Genomics 2011, 12:184. PubMed Abstract | BioMed Central Full Text | PubMed Central Full Text OpenURL

  31. Abyzov A, Urban A, Snyder M, Gerstein M: CNVnator: an approach to discover, genotype, and characterize typical and atypical CNVs from family and population genome sequencing.

    Genome Res 2011, 21:974. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  32. Chen K, Wallis JW, McLellan MD, Larson DE, Kalicki JM, Pohl CS, McGrath SD, Wendl MC, Zhang Q, Locke DP, Shi X, Fulton RS, Ley TJ, Wilson RK, Ding L, Mardis ER: BreakDancer: an algorithm for high-resolution mapping of genomic structural variation.

    Nat Methods 2009, 6:677-681. PubMed Abstract | Publisher Full Text OpenURL

  33. Sindi S, Helman E, Bashir A, Raphael BJ: A geometric approach for classification and comparison of structural variants.

    Bioinformatics 2009, 25:i222-230. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  34. Quinlan A, Clark R, Sokolova S, Leibowitz M, Zhang Y, Hurles M, Mell J, Hall I: Genome-wide mapping and assembly of structural variant breakpoints in the mouse genome.

    Genome Res 2010, 20:623. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  35. Hormozdiari F, Hajirasouliha I, Dao P, Hach F, Yorukoglu D, Alkan C, Eichler E, Sahinalp S: Next-generation VariationHunter: combinatorial algorithms for transposon insertion discovery.

    Bioinformatics 2010, 26:i350. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  36. Ye K, Schulz M, Long Q, Apweiler R, Ning Z: Pindel: a pattern growth approach to detect break points of large deletions and medium sized insertions from paired-end short reads.

    Bioinformatics 2009, 25:2865. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  37. Qi J, Zhao F: inGAP-sv: a novel scheme to identify and visualize structural variation from paired end mapping data.

    Nucleic Acids Res 2011, 39:W567. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  38. Medvedev P, Fiume M, Dzamba M, Smith T, Brudno M: Detecting copy number variation with mated short reads.

    Genome Res 2010, 20:1613. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  39. Bashir A, Volik S, Collins C, Bafna V, Raphael B: Evaluation of paired-end sequencing strategies for detection of genome rearrangements in cancer.

    PLoS Comput Biol 2008, 4:e1000051. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  40. Antonacci F, Kidd J, Marques-Bonet T, Ventura M, Siswara P, Jiang Z, Eichler E: Characterization of six human disease-associated inversion polymorphisms.

    Hum Mol Genet 2009, 18:2555. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  41. Lee S, Cheran E, Brudno M: A robust framework for detecting structural variations in a genome.

    Bioinformatics 2008, 24:59-67. Publisher Full Text OpenURL

  42. Hormozdiari F, Alkan C, Eichler EE, Sahinalp SC: Combinatorial algorithms for structural variation detection in high-throughput sequenced genomes.

    Genome Res 2009. OpenURL

  43. Mills R, Walter K, Stewart C, Handsaker R, Chen K, Alkan C, Abyzov A, Yoon S, Ye K, Cheetham R, Chinwalla A, Conrad D, Fu Y, Grubert F, Hajirasouliha I, Hormozdiari F, Iakoucheva L, Iqbal Z, Kang S, Kidd J, Konkel M, Korn J, Khurana E, Kural D, Lam H, Leng J, Li R, Li Y, Lin CY, Luo R, et al.: Mapping copy number variation by population-scale genome sequencing.

    Nature 2011, 470:59-65. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  44. Altshuler D, Durbin RM, Abecasis GR, Bentley DR, Chakravarti A, Clark AG, Collins FS, De La Vega FM, Donnelly P, Egholm M, Flicek P, Gabriel SB, Gibbs RA, Knoppers BM, Lander ES, Lehrach H, Mardis ER, McVean GA, Nickerson DA, Peltonen L, Schafer AJ, Sherry ST, Wang J, Wilson R, Gibbs RA, Deiros D, Metzker M, Muzny D, Reid J, Wheeler D, et al.: A map of human genome variation from population-scale sequencing.

    Nature 2010, 467:1061-1073. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  45. VCF (Variant Calling Format) version 4.1. [http:/ / www.1000genomes.org/ wiki/ Analysis/ Variant%20Call%20Format/ vcf-variant-call-format-version-41] webcite

  46. Lander E, Waterman M: Genomic mapping by fingerprinting random clones: a mathematical analysis.

    Genomics 1988, 2:231-239. PubMed Abstract | Publisher Full Text OpenURL

  47. Levy S, Sutton G, Ng P, Feuk L, Halpern A, Walenz B, Axelrod N, Huang J, Kirkness E, Denisov G, Lin Y, MacDonald J, Pang A, Shago M, Stockwell T, Tsiamouri A, Bafna V, Bansal V, Kravitz S, Busam D, Beeson K, McIntosh T, Remington K, Abril J, Gill J, Borman J, Rogers Y, Frazier M, Scherer S, Strausberg R, Venter J: The diploid genome sequence of an individual human.

    PLoS Biol 2007, 5:e254. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  48. Novocraft: Novoalign. [http://www.novocraft.com/main/index.php] webcite

  49. Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N, Marth G, Abecasis G, Durbin R, 1000 Genome Project Data Processing Subgroup: The sequence alignment/Map format and SAMtools.

    Bioinformatics 2009, 25:2078. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  50. Xi R, Hadjipanayis A, Luquette L, Kim T, Lee E, Zhang J, Johnson M, Muzny D, Wheeler D, Gibbs R, Kucherlapati R, Park P: Copy number variation detection in whole-genome sequencing data using the Bayesian information criterion.

    Proc Natl Acad Sci USA 2011, 108:E1128-1136. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  51. Metzker M: Sequencing technologies - the next generation.

    Nat Rev Genet 2009, 11:31-46. PubMed Abstract | Publisher Full Text OpenURL

  52. Li H, Durbin R: Fast and accurate short read alignment with Burrows-Wheeler transform.

    Bioinformatics 2009, 25:1754-1760. PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL