PaperlayerView exact revision on arXiv

Source-linked AI summary

CLEVER: Clique-Enumerating Variant Finder

Tobias Marschall, Ivan Costa, Stefan Canzar, Markus Bauer, Gunnar Klau, Alexander Schliep, Alexander Schönhuth

arXiv:1203.0937v2q-bio.GNstat.AP

TL;DR

Structural-variant discovery has not become routine, and small indels remain challenging. CLEVER organizes all paired-end alignments, including concordant reads, into a graph and statistically tests its maximal cliques; it reports strong performance on indels, particularly 20–99 bp, and complementary calls on real data.

  • Problem

    Structural-variant genotyping is not routine, and discovering indels below 500 bp remains challenging, especially amid repetitive-region mapping ambiguity.

    Source: §1 · p. 2

  • Method

    CLEVER organizes all read alignments, including concordant ones, into a graph, enumerates maximal cliques, and statistically evaluates them as candidate indels.

    Source: §1 · p. 2, §2.2 · p. 7

  • Results

    CLEVER outperforms prior insert-size approaches on indels of 20–99 bp and split-read approaches on indels of 50–99 bp and at least 100 bp.

    Source: §3 · p. 11

  • Takeaways & Limitations

    CLEVER detects substantial variants missed by other approaches, particularly in the 20–49 bp range, and its correct calls complement PINDEL’s.

    Source: §3 · p. 11

    The datasets studied assume normally distributed internal segment sizes, although CLEVER also accepts arbitrary distributions.

    Source: §1 · p. 2, §2.1 · p. 5

Abstract

from arXiv · show

Next-generation sequencing techniques have facilitated a large scale analysis of human genetic variation. Despite the advances in sequencing speeds, the computational discovery of structural variants is not yet standard. It is likely that many variants have remained undiscovered in most sequenced individuals. Here we present a novel internal segment size based approach, which organizes all, including also concordant reads into a read alignment graph where max-cliques represent maximal contradiction-free groups of alignments. A specifically engineered algorithm then enumerates all max-cliques and statistically evaluates them for their potential to reflect insertions or deletions (indels). For the first time in the literature, we compare a large range of state-of-the-art approaches using simulated Illumina reads from a fully annotated genome and present various relevant performance statistics. We achieve superior performance rates in particular on indels of sizes 20--100, which have been exposed as a current major challenge in the SV discovery literature and where prior insert size based approaches have limitations. In that size range, we outperform even split read aligners. We achieve good results also on real data where we make a substantial amount of correct predictions as the only tool, which complement the predictions of split-read aligners. CLEVER is open source (GPL) and available from http://clever-sv.googlecode.com.

1 Introduction

CLEVER addresses the difficulty of discovering structural variants by using all read alignments, including concordant ones, to identify candidate indels. It combines maximal-clique enumeration with statistical evaluation of the resulting alignment groups.

1 Introduction

  • Structural-variant genotyping is not routine; indels below 500 bp remain challenging, and repetitive regions add read-mapping ambiguities.Prior approaches use coverage, insert-size, or split-read evidence; split-read aligners usually have an advantage on smaller indels and perform worse on larger ones.Source: §1 · p. 2
  • On simulated and real data, CLEVER outperforms prior insert-size approaches, compares favorably with two split-read aligners, and predicts >20% of simulated true 20–49 bp deletions as the only tool.Its correct calls also complement those of the split-read aligner PINDEL.Source: §1 · p. 3

1.1.1 Graph-Based Framework

  • CLEVER builds a graph from all read alignments, where edges connect overlapping alignments likely to stem from the same allele and maximal cliques represent consistent groups.A specially engineered procedure enumerates all maximal cliques despite graphs with more than 10^9 nodes in the instances considered.Source: §1.1.1 · pp. 3–4

1.1.2 Significance Evaluation

  • A sample-size Z-test makes smaller interval-length deviations significant for larger groups, so each maximal clique is tested for common concordance or discordance.The approach also weights alignments by their probabilities of being correctly placed and corrects for multiple tests.Source: §1.1.2 · pp. 4–5
  • The procedure applies a local Bonferroni correction for coverage fluctuations and a Benjamini–Hochberg correction for multiple hypothesis testing overall.Only MoDIL among the prior approaches is noted as also using Benjamini–Hochberg correction.Source: §1.1.2 · pp. 4–5

2 Methods

CLEVER organizes all well-oriented read alignments into a graph whose maximal cliques represent compatible groups, then tests those groups for insertions or deletions. Its workflow enumerates maximal cliques, evaluates their support statistically, and derives variant parameters from significant groups.

2.1 Notations, Definitions and Background

  • CLEVER retains all well-oriented read alignments, including concordant reads; the datasets use normal insert-size statistics, estimated robustly, while arbitrary distributions are also allowed.The empirical interval-length distribution is fat-tailed because it reflects structural variation between donor and reference.Source: §2.1 · p. 5
  • Edges connect overlapping alignments from different reads when statistical tests do not reject a shared allele; maximal cliques are maximal groups of mutually compatible alignments.Compatibility considers both insert-length consistency and whether the overlap can contain the putative variation.Source: §2.1 · pp. 6–7

2.2 CLEVER: Algorithmic Workflow

  • For each maximal clique, CLEVER computes deletion and insertion p-values, interprets small values as support, and controls each variant type’s false discovery rate at 10%.The p-value calculations include a correction for the number of alignment subsets tested at a location.Source: §2.2 · pp. 7–8
  • Significant groups are parameterized by deletion or insertion length and a breakpoint placing the predicted variant in the middle of the alignments’ shared internal-segment intersection.Deletions use a left breakpoint and length; insertions use a breakpoint and inserted-sequence length.Source: §2.2 · p. 7
  • A left-to-right endpoint scan maintains active cliques, extends them through compatible neighbors, and outputs cliques when intervals end, removing duplicates and nonmaximal subsets.The stated runtime is O(m(log m + kc^2) + s), with k bounding local coverage, c active cliques, and s output size.Source: §2.2 · pp. 7–8

3 Results and Discussion

CLEVER outperforms prior insert-size approaches on indels of 20–99 bp and achieves favorable results for longer indels, while making correct calls missed by other tools. Its approach enumerates statistically contradiction-free alignment groups and evaluates them as potential variants.

Experiments and results

  • The benchmark compares five insert-size approaches and two split-read aligners on simulated Venter and real NA18507 data, but incomplete real-data annotations mean real-data results show trends only.Table 1 groups recall, precision, exclusive predictions, and F-measure by indel size range and dataset.Source: Table 1 · p. 9, §3 · p. 10

20–49 bp

  • For 20–49 bp indels, CLEVER outperforms all other approaches on simulated data and is the best insert-size approach on real data, while making substantial exclusive calls.PINDEL achieves the best rates on real data; 80–90% of CLEVER’s calls come significantly close to a real indel.Source: §3 · p. 10

50–99 bp

  • For 50–99 bp indels, CLEVER achieves substantially better recall and more exclusive calls than PINDEL on real data and best overall performance on simulated data.When allowing breakpoint offsets or integrating correct alignments, CLEVER’s precision rises from 60–72% to 72–96% across the categories.Source: §3 · p. 11

100–50000 bp

  • For indels ≥100 bp, CLEVER achieves the most favorable performance rates, although Breakdancer, HYDRA, and VariationHunter also make decisive contributions.The results identify 20–100 bp as the current challenge range for indel discovery.Source: §3 · p. 11

MoDIL

  • On chromosome 1, CLEVER outperforms MoDIL by a factor of ≈1000 in runtime, while MoDIL incurs performance losses relative to CLEVER across categories.MoDIL was run only on chromosome 1 because of its excessive runtime requirements.Source: §3 · p. 11

Accuracy of breakpoint and length predictions

  • CLEVER’s correct calls complement those of split-read aligners, while the compared split-read approaches outperform insert-size approaches in breakpoint and length prediction accuracy.Among insert-size approaches, CLEVER and GASV are most precise for 20–49 bp and 100–50000 bp; Breakdancer has favorable values for 50–99 bp calls.Source: §3 · p. 11

Conclusion

  • CLEVER outperforms prior insert-size approaches on 20–99 bp indels, achieves favorable values for longer indels, and makes substantial contributions especially in the 20–99 bp range.It also detects substantial numbers of variants missed by other approaches, particularly for 20–49 bp indels.Source: §3 · p. 11
  • CLEVER combines an algorithm that enumerates maximal statistically contradiction-free alignment ensembles as max-cliques with a statistical procedure for calling variant-indicating cliques.The approach is generic to variant type; the authors identify predicting inversions and incorporating split-read information as future work.Source: §3 · p. 11

A Appendix: Engineering the CLEVER algorithm

CLEVER’s engineering uses bitvectors and efficient node lookup to make clique enumeration practical, while controlling local alignment coverage. The appendix reports hundreds of millions of computed cliques and shows how the implementation tracks active-set and bit-vector capacity distributions.

A Appendix: Engineering the CLEVER algorithm

  • Bitvectors represent active cliques, while a binary search tree sorted by segment length helps find candidate vertices efficiently.Bit-parallel operations compute intersections with the current vertex’s neighborhood.Source: A Appendix: Engineering the CLEVER… · pp. 11–12
  • When active nodes reach bit-vector capacity, CLEVER discards inactive nodes, sets capacity to twice the remaining active-node count, and repacks the bitvectors.This strategy balances less frequent memory reorganization against keeping active sets manageable.Source: A Appendix: Engineering the CLEVER… · pp. 12–15
  • CLEVER removes alignments with interval length ≥50,000 and, if needed, alignments with weight P0(A) < 1/625 to limit local coverage to about 500 alignments.The stated rationale includes treating deletions of at least 50,000 bases as relatively easy and allowing at most 25 alignments per read end.Source: A Appendix: Engineering the CLEVER… · p. 15
  • The appendix records active-clique counts, active-node counts, and bit-vector capacities after each alignment pair; delayed removal and capacity doubling can produce capacities above 500.The distributions are shown for both Venter and NA18507.Source: Figure 3 · p. 12, Figure 4 · p. 12, Figure 5 · p. 13
  • 647,944,355 cliques were computed from Venter alignments and 1,193,764,528 from NA18507 alignments.The appendix also plots histograms of active cliques, active nodes, and bit-vector capacities for both datasets.Source: Figure 3 · p. 12, Figure 4 · p. 12, Figure 5 · p. 13

A.1 Runtime Analysis

The appendix analyzes CLEVER’s clique-enumeration runtime, describes an approximation for a statistical quantity, and documents evaluation-pipeline settings. It also specifies how tools’ outputs were converted into exact indel predictions.

A.1 Runtime Analysis

  • The stated runtime is O(m(log m + kc^2) + s), where k bounds local alignment coverage, c is the maximum active-clique count, and s is output size.Sorting costs O(m log m); the remaining analyzed intersections contribute O(mkc^2).Source: §A.1 · p. 15
  • With k = 500, only 1% of observed active-clique sets exceed 268 cliques, and more than 99% of active cliques contain fewer than 236 nodes.The authors cite these observed sizes as one reason practical behavior is better than the worst-case guarantees suggest.Source: §A.1 · p. 15
  • Bit-parallel operations reduce intersection costs by a factor of word size w, yielding a stated runtime of O(m(log m + k + k/w·c^2) + s).The algorithm avoids explicitly constructing the read alignment graph and uses a binary search tree with bit-parallel operations.Source: §A.1 · p. 15

B Appendix: Approximation of (8)

  • The approximation is designed to upper-bound PH0(C) for multiple-testing correction, and it is exact when all alignments in C have equal weight.The authors state that this upper bound can be computed in polynomial time.Source: B Appendix: Approximation of (8) · pp. 16–17

C Appendix: Pipeline Details

  • The evaluation forces tools to produce exact predictions; CLEVER uses BWA alignments, while BWA permits up to 25 reported alignments per read end.When a tool does not provide exact calls, the authors derive coordinates or lengths from its output.Source: C Appendix: Pipeline Details · p. 17, §C.2 · p. 17, §C.10 · p. 20
  • The pipeline documents separate output-to-call conversions for HYDRA, GASV, PINDEL, BreakDancer, VariationHunter, MODIL, and SV-seq2.For example, GASV is used for deletions only, while SV-seq2 does not report insertion lengths.Source: §C.3 · p. 18, §C.4 · p. 18, §C.5 · p. 18

D Appendix: Fixed-Distance Hits

This appendix defines an alternative fixed-distance criterion for counting indel calls as hits and assesses whether such hits are likely by chance. It distinguishes the distance and length conditions from the overlap-based criterion used in the main text.

D Appendix: Fixed-Distance Hits

  • A fixed-distance hit uses insertion breakpoint distance or deletion-center distance, while still requiring the length deviation to remain below the same threshold.For long deletions the distance criterion is stricter than requiring any overlap; for short deletions, nearby non-overlapping calls may qualify.Source: D Appendix: Fixed-Distance Hits · p. 21
  • The appendix reports high-accuracy and relaxed hit tables using thresholds of 20 and 100 for both distance and allowed length deviation.This alternative is presented because long indels can overlap despite widely separated predicted and true breakpoints.Source: D Appendix: Fixed-Distance Hits · p. 21
  • For Venter variants of length at least 10, the estimated random-success probability is at most 4.4 × 10^-4 for threshold-20 deletion breakpoints and about 0.002 at threshold 100.The calculations do not account for prediction length, which would make random success still less likely.Source: D Appendix: Fixed-Distance Hits · p. 21

D.1.1 Venter

The Venter results are organized by indel length range and prediction method, with insertion and deletion metrics shown separately. The supplied passage identifies the evaluated ranges and truth-set sizes but provides no metric values.

D.1.1 Venter

  • The 20–49 bp range contains 8,786 true insertions and 8,502 true deletions, with precision, recall, and exact-match F columns indicated.The table heading also distinguishes Venter insertions and deletions by method.Source: §D.1.1 · p. 22
  • The 50–99 bp range contains 2,024 true insertions and 1,822 true deletions.The supplied row labels the range but gives no reported metric values.Source: §D.1.1 · p. 22
  • The 100–50,000 bp range contains 3,101 true insertions and 2,996 true deletions.The supplied row labels the range but gives no reported metric values.Source: §D.1.1 · p. 22

D.1.2 NA18507

The supplied table fragments divide NA18507 and Venter calls into indel length ranges and identify insertion and deletion counts for some ranges.

D.1.2 NA18507

  • NA18507’s 20–49 bp range contains 2,295 true insertions and 2,192 true deletions.The fragment also lists RPr., Rec., and Exc. columns for insertions and deletions.Source: §D.1.2 · p. 23
  • The cited passage reports a 50–99 bp length range with 303 true insertions and 294 true deletions, giving the true insertion and deletion counts for that range.Source: §D.1.2 · p. 23
  • The NA18507 table includes a 100–50,000 bp length range.Source: §D.1.2 · p. 23

D.2.1 Venter

  • Venter’s 20–49 bp range contains 8,786 true insertions and 8,502 true deletions.The fragment lists precision, recall, exception, and F columns for insertions and deletions.Source: §D.2.1 · p. 24
  • Venter’s 50–99 bp range contains 2,024 true insertions and 1,822 true deletions.Source: §D.2.1 · p. 24

D.2.2 NA18507

The NA18507 table fragments list insertion and deletion evaluation across three indel length ranges.

D.2.2 NA18507

  • The NA18507 20–49 bp range contains 2,295 true insertions and 2,192 true deletions.The fragment lists RPr., Rec., and Exc. columns for both variant types.Source: §D.2.2 · p. 25
  • The NA18507 50–99 bp range contains 303 true insertions and 294 true deletions.The fragment lists the length range and true-variant counts.Source: §D.2.2 · p. 25
  • The NA18507 table includes a 100–50,000 bp length range.Source: §D.2.2 · p. 25

E Appendix: Statistics on Length Difference and Distance

Split-read approaches make the most accurate predictions, while CLEVER usually has good length-difference rates but not the best breakpoint-distance values.

E Appendix: Statistics on Length Difference and Distance

E.1 Venter

The Venter table reports CLEVER’s insertion and deletion distance and length-difference metrics across three size ranges.

E.1 Venter

  • CLEVER’s Venter 20–49 bp row reports insertion Dist. 16.5 and Len.Diff. 8.6, and deletion Dist. 14.7 and Len.Diff. 9.6.Source: §E.1 · p. 27
  • CLEVER’s Venter 50–99 bp row reports insertion Dist. 28.9 and Len.Diff. 18.8, and deletion Dist. 27.0 and Len.Diff. 13.9.Source: §E.1 · p. 27
  • CLEVER’s Venter 100–50,000 bp row reports insertion Dist. 35.9 and Len.Diff. 23.8, and deletion Dist. 24.4 and Len.Diff. 13.0.Source: §E.1 · p. 27

F Appendix: External Error Sources

The appendix examines how alignment quality and repetitive mapping affect structural-variant predictions. True alignments generally perform best, but the reported comparison suggests repetitive mapping has a larger effect than mapper imperfections in most cases.

F Appendix: External Error Sources

  • CLEVER was run on true alignments and BWA alignments augmented with missing true mappings, with performance reported for indel-length ranges 20–49, 50–99, and 100–50 000 bp.The corresponding true insertion and deletion counts were 8,786 and 8,502; 2,024 and 1,822; and 3,101 and 2,996, respectively.Source: F Appendix: External Error Sources · p. 28
  • On the augmented-alignment dataset, performance losses were mainly attributed to mistaken alignment-quality scores, pointing to Phred-score quality as another error source, particularly for multiply mapped reads.The augmented dataset included true mappings for every read while retaining alternative mappings reported by BWA.Source: F Appendix: External Error Sources · p. 28
  • True alignments yielded the best results in most cases, confirming alignment quality matters, although they did not lead in every case.The authors report no explanation for those exceptions.Source: F Appendix: External Error Sources · p. 28
  • In most cases, the F-measure gap between BWA+True and True exceeded the gap between BWA and BWA+True, suggesting repetitive mapping has the stronger negative influence.The authors note that true alignments do not yield the best results in every case and say they have not found an explanation.Source: F Appendix: External Error Sources · p. 28

G Appendix: MoDIL Results on Chromosome 1

Because MoDIL has extraordinarily long runtimes, the appendix evaluates it only on simulated reads from Venter’s chromosome 1. The results are presented alongside other tools run on the same restricted dataset.

G Appendix: MoDIL Results on Chromosome 1

  • MoDIL’s extraordinarily long runtimes restricted its evaluation to simulated reads from chromosome 1 of Venter’s genome.Other tools were also run on this restricted dataset for an unbiased comparison.Source: G Appendix: MoDIL Results on… · p. 29
  • The chromosome 1 table covers 20–49 bp indels, with 644 true insertions and 640 true deletions.It reports precision, recall, exception, and F statistics for insertions and deletions.Source: G Appendix: MoDIL Results on… · p. 29
  • The table also covers 50–99 bp indels (153 true insertions; 130 true deletions) and 100–50 000 bp indels (223 true insertions; 198 true deletions).The excerpt includes a row reporting N/A for SV-seq2 insertions and 0.0 precision and recall for deletions in the 100–50 000 bp range.Source: G Appendix: MoDIL Results on… · p. 29
Loading 1203.0937v2…