A geometric approach for classification and comparison of structural variants

Abstract

Motivation: Structural variants, including duplications, insertions, deletions and inversions of large blocks of DNA sequence, are an important contributor to human genome variation. Measuring structural variants in a genome sequence is typically more challenging than measuring single nucleotide changes. Current approaches for structural variant identification, including paired-end DNA sequencing/mapping and array comparative genomic hybridization (aCGH), do not identify the boundaries of variants precisely. Consequently, most reported human structural variants are poorly defined and not readily compared across different studies and measurement techniques.

Results: We introduce Geometric Analysis of Structural Variants (GASV), a geometric approach for identification, classification and comparison of structural variants. This approach represents the uncertainty in measurement of a structural variant as a polygon in the plane, and identifies measurements supporting the same variant by computing intersections of polygons. We derive a computational geometry algorithm to efficiently identify all such intersections. We apply GASV to sequencing data from nine individual human genomes and several cancer genomes. We obtain better localization of the boundaries of structural variants, distinguish genetic from putative somatic structural variants in cancer genomes, and integrate aCGH and paired-end sequencing measurements of structural variants. This work presents the first general framework for comparing structural variants across multiple samples and measurement techniques, and will be useful for studies of both genetic structural variants and somatic rearrangements in cancer.

Availability: http://cs.brown.edu/people/braphael/software.html .

Fig. 1.

Derivation of regions of uncertainty (breakpoint regions) from ESP and aCGH data. (A) (Top panel) In ESP, or paired-end mapping, both ends of a fragment of a test genome are sequenced and aligned to the reference genome. Here, alignment of ends of fragments C and D yields ES pairs (x_C, y_C) and (x_D, y_D) on the reference genome that suggest an inversion. (Bottom panel) The intersection of breakpoint regions defined by Equation (1) indicates the possible locations of inversion breakpoints a and b that are consistent with the ES pairs. (B) (Top panel) In an aCGH experiment, the reference genome is segmented into regions of equal copy number according to measurements at genomic probes (boxes). A deletion with breakpoints a and b is identified as a change in copy number between probes p_i and p_i+1 and between probes p_j and p_j+1. (Bottom panel) The intervals [p_i, p_i+1] and [p_j, p_j+1] define a rectangular breakpoint region. This region is intersected with the breakpoint region defined by an ES pair (x_C, y_C) to refine the locations a and b of the deletion.

Fig. 2.

Breakpoint regions determined by fragments from Kidd et al. (2008) whose orientations suggest an inversion variant(s). Breakpoint region 2 has distinct intersections with regions 1 and 3, and thus iterative merging of breakpoint regions will not identify all intersections.

Fig. 3.

Examples of the three events of the plane sweep: (A) addition, (B) intersection and (C) removal. In each case black dots label the points recorded in the cyclic lists a and b (indicated as dashed paths) that form ℛ. In addition, we show in {}'s the labels assigned to the intersecting breakpoint regions.

Fig. 4.

Geometric analysis of inversion polymorphisms from Kidd et al. (2008) reveals disparities between the reported boundary of variants (black dots) and the intersections of breakpoint regions. (A) An inversion on chr1 with 79 reported supporting clones from all nine individuals has no point in common to all breakpoint regions. The number x next to each of the three regions indicates a clone from individual labeled ABCx in Kidd et al. (2008) is present in the cluster; a ‘G’ indicates the G95 individual from Tuzun et al. (2005). The bottom right region contains clones from all nine individuals, while individual ABC13 has clones from all three regions suggesting multiple distinct structural variants or mapping difficulties at this locus. (B) An inversion from chr3 with 22 supporting clones from all eight HapMap individuals. We examined one fully sequenced clone (dashed trapezoid) from individual ABC7 and found two possible inversion breakpoints (black squares). Both of these lie in the intersection of all breakpoint regions but are ∼37 kb from the reported boundary.

Fig. 5.

Intersection of 33 inversion breakpoint regions (blue) and 4 deletion breakpoint regions (red), indicates common genomic location of two structural variants.

Fig. 6.

Intersection between six breakpoint regions from ESP data (blue trapezoids) and two breakpoint regions determined by aCGH (red rectangle) on chr17 in the BT474 breast cancer cell line. In this case, the spacing between aCGH probes provides a more precise localization of the breakpoint region that the paired-end sequencing data.