BACKGROUND
the detection of genetic variation between individuals is a key challenge in current research in genome biology.
this variation includes single nucleotide polymorphisms , structural variants  and copy number variants  such as deletions, insertions or duplications, as well as copy number invariant changes like translocations or inversions.
snps are used extensively to link phenotypic traits with associated genotypes in genome-wide association studies
<cit>  and to infer relationships in evolutionary studies
<cit> .
svs can provide additional insights into the genomic causes of phenotypic diversity
<cit> .
moreover, it is assumed that the total number of nucleotides spanned by svs greatly exceeds that of snps in human and plants
<cit> .
hence svs will be included more and more into these studies
<cit> .
furthermore, svs are associated with different types of human diseases
<cit>  and plant phenotypes
<cit> .
compared to snp identification, the detection of larger divergent sequences remains a challenging task.
we here present a machine learning approach to predict svs based on ngs.
traditionally, structural variants, in particular deletions and duplications, have been identified using array-based technologies
<cit> , but these strategies suffered from a limited size and localization resolution, which is dependent on the density of probes or known markers.
with the advent of ngs methods, whole-genome studies became feasible.
small insertions and deletions  up to a few base pairs in length were called by sensitive alignment tools in the routine re-sequencing process
<cit> .
however, the detection of larger structural variants based on depth-of-coverage
<cit>  or paired-end mapping
<cit>  methods could not reduce the sv size and localization resolution to the one base pair level.
doc
<cit>  algorithms detect regions with absent  or significantly elevated  coverage, but are not able to determine the exact insertion location on the base pair level of the duplicated sequence.
pem
<cit>  methods exploit the fact that the distance between the alignment locations of read pairs on a reference genome  usually follow a normal distribution.
clusters of read pairs mapping to the same genomic regions, whose distance is much shorter  than expected can be explained by an insertion  in the newly sequenced individual compared to the reference genome.
the standard deviation and the mean of the insert size distribution define the sensitivity of this method.
recently, so-called split-read mapping approaches  were introduced to pinpoint structural variants and especially indels in the genome correctly to the base pair level
<cit> .
these methods use mapped-unmapped read pairs  from a paired-end alignment performed by existing short read mapping tools.
the mapped partner serves as anchor to realign the unmapped partner using alignment algorithms allowing for long-range gaps in both the reference sequence  or the read .
we will refer to the initial mapping which identifies murs as first and the split read alignment as second mapping pass throughout this manuscript.
deletions up to a few tens or hundreds of base pairs in length can be identified by array based, doc and pem approaches, while conventional short read alignments are designed to find only deletions of a few base pairs.
in contrast, srm predictions can in principle span the whole range of deletion lengths.
however, the size of insertions is limited, and spurious alignments of the indel-flanking read parts might lead to multiple contradicting indel candidates.
both limitations directly depend on the read length and are thought to be counterbalanced by longer sequences from advanced technologies.
finally, deletions can be identified by limited de novo assembly methods, but they are not yet used routinely and require whole-genome alignments or close relative genomes for comparisons.
though a large number of software packages for indel prediction from ngs data have been developed, application of these methods to identical data sets reveals little overlap
<cit> .
this is caused by different indel identification strategies.
to reduce the number of false positive indel candidates, srm methods, such as pindel
<cit> , rely on conservative realignment strategies.
here, solely perfect and uniquely mapped reads are considered for further analysis.
moreover, the realignment of the unmapped partner has to be mismatch-free as well.
these constraints reduce the set of possible indel candidates drastically.
existing srm programs report an indel as soon as two independent reads support the same sv, and if their partner reads lie within concordant insert sizes
<cit> .
other methods use several alignment features as evidence of an indel.
however, either relying on logical rules
<cit>  or on generative probabilistic models
<cit> , they require an empirically defined threshold, above which a candidate is a true sv.
the most reliable way to verify indels is by capillary sequencing, but this is unfeasible for a genome-wide scan.
thus, to identify a comprehensive set of indels, a non-conservative mapping strategy is needed that takes non-unique and non-perfect mapping reads into account.
furthermore, to rate their trustworthiness, an evaluation method is needed which collects information about numerous alignment features from different approaches and automatically weighs their contributions.
here we introduce an extended realignment split read strategy to identify a comprehensive set of indel candidates.
a de novo machine learning method is applied to discriminate between ‘true’ and ‘false’ indel candidates based on more than  <dig> alignment features, which can be derived from any short read mapping tool.
its core is a support vector machine
<cit> , a discriminative classifier that is trained on diverse alignment information on indel examples validated by reliable sanger sequencing.
our svm approach avoids the step of defining thresholds for each feature by automatically learning them from sanger validated training data.
we show that a commonly used criterion, namely the number of split read pairs supporting the same indel, is not sufficient to distinguish true indels from false candidates, but that additional features can accurately predict bona fide svs.
concomitantly, our method reports the contribution of each feature to this decision process.
our approach was applied to  <dig> genomes of arabidopsis thaliana <cit>  and its validity demonstrated by recovering a highly similar population structure of the analyzed strains solely based on positively classified indels compared to taking snp data as a basis.
RESULTS
indel candidate detection
we performed a custom split read alignment method to retrieve indel candidates from the arabidopsis thaliana strain ice <dig> from phase i of the  <dig> genomes project
<cit> .
the read lengths ranged from  <dig> to  <dig> bp with an average sequencing depth of 21x.
all mapped-unmapped read pairs  were retrieved from the available alignments from cao et al.
<cit> , which allowed  <dig> base pair differences between read and reference, of which at most  <dig> could be gaps.
the mapped partner may have multiple alignment positions across the whole genome.
because of many ambiguous alignments due to the high repetitivity of centromeric sequences, all murs within centromeres were excluded.
the unmapped partners of the murs were mapped against col- <dig>  in a  <dig>  bp window downstream of the mapped partner using gotoh’s alignment algorithm
<cit> , allowing for long-range gaps as well as additional snps or few base pair-sized indels .
all best-scoring alignments were reported and indels with a minimum support of two reads constituted the indel candidate set to be further evaluated.
feature selection
the split read alignment approach identified  <dig>  potential indel candidates for the arabidopsis thaliana strain ice <dig>  we randomly selected  <dig> deletion and  <dig> insertion candidates across all chromosomes from this set and labeled them as true or false after sanger sequencing.
thus, we retrieved two training sets.
the training corpus for deletions consisted of  <dig> correctly and  <dig> falsely labeled examples and the training corpus for insertions of  <dig> true and  <dig> false ones.
these sets were used to train a svm
<cit> .
pindel
<cit>  uses the number of split-read alignments supporting an indel with identical genomic coordinates as the only evidence for an indel.
in a first study, only this alignment feature was used for classification .
the f1-based training was contrasted to the use of several alignment characteristics,  <dig> for insertions  and  <dig> for deletions .
these features can be grouped into four main categories .
the first considers the number of uniquely mapped reads  and non-uniquely mapped reads  overlapping the sequence space within a deletion.
since this is not determinable for insertion signatures, this feature is only available for deletions.
the second group comprises the number of umrs and n-umrs  <dig> bp downstream as well as  <dig> bp upstream of the indel candidate to represent the coverages to the right and left where  <dig> bp reflects approximately the maximum read length.
a ‘true’ deletion should show either zero or a low number of umrs within the deleted region compared to the umr-coverage up- and downstream thereof, whereas a certain number of n-umrs might be tolerated.
the third group of features examines the concordance of snp and short indel calls detected by the two mapping passes .
since these variations are compared to each other position-wise, short indels are considered as consecutive single position variants .
these features can be interpreted as a check if the aligned reads of the first mapping pass in the vicinity of an indel derive from the same haplotype as the split reads spanning the indel.
the last category includes general attributes such as the indel length and the split read alignment support of identically-located indels.
discriminative training
we trained a svm
<cit>  using a simple-to-interpret linear kernel on all three sets of features  performing a 10-fold cross-validation for deletions and a 5-fold cross-validation for insertions and repeated each cross-validation  <dig> times .
the resulting average area under the receiver operating characteristic curves  and average specificity-sensitivity-break-even-points   suggest that the f1-based classification did not notably exceed the performance of a random guess for deletions  and performs slightly better for insertions , whereas the use of  <dig>  and  <dig> features  reveal high concordance with the true classification.
the training of the svm based on a linear kernel enabled us to identify the contributions of each feature to an indel prediction.
positive weights contribute to the support, and negative to the rejection of a candidate .
interestingly, the criteria for deletions and insertions notably differ from each other.
while the strongest argument in favor for deletions is the number of sv supporting reads, it is the sequence length for insertions.
furthermore, the agreement of spvs between the first and the second mapping pass contributes more to the acceptance of insertions, but is used as an indication against the trustworthiness of deletions.
this effect might be explained by alignment errors by the first mapping pass close to deletions causing false positive spv calls.
our classifier for insertions is trained on a dataset including  <dig> true insertions.
due to the limited size of this training dataset, it is to be expected that larger training datasets will further improve the prediction performance.
indel prediction
applying our machine learning approach with the f13/f <dig> feature set to indel candidates of strain ice <dig> positively classified  <dig>  out of  <dig>  deletions in total , and  <dig> from  <dig> insertions , respectively.
the length of deletions ranged from  <dig> to  <dig>  bp with a mean of  <dig> bp and a median of  <dig> bp.
for insertions the length ranged from  <dig> to  <dig> bp with a mean and median of  <dig> bp.
thus, the svm was capable to extract information from the defined features leading to falsifications of indel candidates.
’false’ svs can be attributed to spurious mappings dependent on the length of the split read fragments or to multiple best-scoring alignments across the reference.
next, we compared our predictions of indels in the strain ice <dig> to those identified by two versions of pindel
<cit>  .
the minimum length of deletions was set to  <dig> bp for all three sets, and the maximum deletion size constituted  <dig>  bp due to the adjustable restriction of the alignment space.
pindel detected a total of  <dig>   and  <dig>   deletions larger than  <dig> bp.
<dig> %  of pindel’s deletions were shared among all unclassified deletions of our approach.
the svm classification identified  <dig>  and  <dig>  false positive deletions among the pindel candidates.
further, our gotoh approach detected an additional set of  <dig>   and  <dig>   positively classified deletions.
this can be explained by different mapping strategies.
pindel
<cit>  in version  <dig>  requires uniquely and error-free mapped reads and allows only split read alignments where the read partners are aligned within two times the average insertion size.
on the contrary, our svm approach follows a less conservative re-alignment strategy by analyzing non error-free and multiple best-scoring alignments of the same read.
moreover, we tolerated split read mappings anywhere within the alignment window, which results in a larger candidate set by allowing the detection of svs in highly divergent regions.
the subsequent classification compensates for these introduced levels of uncertainty.
indeed, sanger sequencing revealed  <dig>  deletions, where the read partners showed discordant insert sizes.
furthermore, a 61bp deletion, which was included in the training set and falsified by sanger sequencing, was reported by pindel, but correctly classified as false by our svm.
this deletion would have proposed a potential frameshift in a coding region.
due to general alignment restrictions, detecting insertions is limited in terms of their length.
aligning a short sequence against a long one by introducing a series of gaps into the long sequence at the same time leads necessarily to an inferior alignment score.
thus, pindel  and our approach share merely 15% of all insertions.
abyzov et al.
<cit>  investigated exactly this problem and proposed an improved alignment algorithm called age.
applying this algorithm we could increase the number of shared insertions to 35%.
indel detection and prediction on  <dig> genomes
next, we detected and classified indels in  <dig> accessions of arabidopsis thaliana from the first phase of the  <dig> genomes project
<cit> .
the average coverage of strains was 17x.
by using a  <dig>  bp alignment window, on average ∼ <dig>  positive deletions and ∼ <dig> positive insertions were reported per strain, the largest being  <dig>  bp long.
combining similarly localized indels of identical length in different strains revealed  <dig>  non-redundant deletions and  <dig>  insertions in this population.
altogether, they span over  <dig> mb in total.
almost half, ∼44%, were shared among more than one strain .
we found  <dig> long-range deletions spanning at least one complete gene sequence of the tair <dig> annotation with an average allele frequency of ∼ <dig>  .
of those deletions  <dig> were classified as whole gene losses if there was no unique read coverage within the deletion  and sufficient coverage in the same-sized flanking regions , as determined by the first mapping pass.
their average allele frequency was ∼ <dig>  .
spurious read mapping within the deletion, ambiguous split read alignments, gene translocations or heterozygous deletions could explain long-range deletions not meeting the aforementioned criteria.
as expected, only a minority  of indels overlap with coding regions and have a potential deleterious effect on proteins .
indels that do not alter the open reading frame of a gene outnumber those that do by almost two to one .
however, the prediction of amino acid or framshift changes has been performed for each sv separately without considering potential nearby svs.
it is known that additional nearby variants can compensate for frameshifts
<cit> , thus the number of protein-changing svs reported here might still be an overestimate.
population structure
to further assess our method, we attempted to recover the population structure of the  <dig> genomes with the predicted indels.
to this end, three principal component analyses
<cit>  were performed: pca1) on our  <dig>  positively classified, non-private  indels , pca2) on the  <dig>  non-private indels identified by the program pindel
<cit>   , and pca3) on the  <dig>  non-private indels identified by the program pindel .
pca <dig> can successfully reconstruct the population structure, even slightly more distinctive as a pca with non-private snps
<cit> .
the first principal component distinguished the western and middle european accessions from the caucasian and russian individuals, explaining a variance of 20%.
the second principle component with a variance of 6% was – as in cao et al.
<cit>  – not completely aligned with the latitude of the accessions.
interestingly, the outlier yeg- <dig> from the caucasus found by cao et al.
was positioned near the south russian and east asian cluster in our analysis as well.
pca <dig> and pca <dig> revealed that the reported indels of the program pindel contain less information about population structure compared to our method.
furthermore, the clustering of the subpopulations in pca <dig> is much more differentiable as in pca <dig> and pca <dig>  the larger set of indels due to the more non-conservative re-alignment strategy and the removal of false indels  seem to reflect the population structure more clearly, suggesting low rates of both false positives and false negatives.
discussion
we present a discriminative machine learning-based approach for detecting true structural variants among indel candidates.
the key benefit of using a discriminative model is to learn to distinguish between true and false candidates based on a sanger validated ground truth, thereby reducing the false positive rate among predicted indels.
we use our method on indel candidates generated via an exact gotoh
<cit>  re-alignment of paired-end reads, for which one partner could not be mapped.
by considering multiply mapped reads on the whole genome and non-error free reads as well as accepting all mappings within the entire alignment window we receive a larger set of potential indel candidates.
consequently, this non-conservative proceeding increases the chances for finding more true positives, but on the other hand tends to identify more false positives as well.
due to that fact it is essential to accurately classify indel candidates using our machine learning approach.
conceptually, our machine learning approach for true indel detection can be combined with any kind of alignment strategy and candidate generation scheme.
indeed, to be able to detect more insertions a different alignment method can be useful.
with the gotoh approach, shorter insertions are preferentially called than longer insertions in a pairwise alignment due to the reduced number of nucleotide matches  the longer the insertion is.
abyzov et al.
developed an alignment tool called age
<cit>  to better call long insertions.
their method was used on the ice <dig> genome in our framework and improved the overlap of insertions between pindel and the gotoh approach from 15% to 35%.
current methods for indel scoring, which either rely on logical rules
<cit>  or generative probabilistic models
<cit> , have to manually define a threshold above which candidates are predicted to be true structural variants.
our machine learning approach avoids this step by automatically learning the threshold from the sanger validated training data.
furthermore, all non-discriminative methods for scoring indel candidates have to solve the difficult task of how to weight different types of evidence for the occurrence of an indel.
unlike these methods, our discriminative approach automatically learns the weights of different features.
in addition, the automatic weighting of features indicates which features are relevant and which ones are less relevant for indel detection.
from our results, we can confirm that our discriminative indel detection benefits from combining several features
<cit> .
the features we selected contain information that can reliably distinguish between true indels and false candidates as demonstrated by the consistent reconstruction of population structure based on true predicted indels.
furthermore, we showed that tools not relying upon a classification step may lead to spurious biological interpretations.
here, pindel
<cit>  identified a deletion candidate causing a potential frameshift, which our post-classification method predicted to be a false one; this prediction was confirmed by one of the sanger sequences.
the classifier was trained on a corpus of reads from a paired-end library sequenced to 21-fold coverage.
our method is robust to changes in fold coverage if the features that are derived from the read alignments, scale linearly with or are independent of sequencing depth.
it is expected, that longer reads will improve our strategy since the longer the indel-flanking read sequences the less ambiguous split read alignments will be retrieved.
the feature normalization we perform accounts for this fold change.
to apply our method in different species, one would need to create a new sanger validated dataset to account for its particular genomic properties such as the degree of heterozygosity or repetitiveness.
however, to circumvent laborious sanger sequencing, the increasing number of de novo assembled genomes or structural variant databases could serve as an alternative and extensive ground truth in future studies.
the software, sanger validated training data and all annotated indels for the  <dig> genomes are available at
http://agkb.is.tuebingen.mpg.de/forschung/sv-m/.
CONCLUSIONS
we showed that accurate indel detection consists of two steps – the realignment of unmapped reads and the post-classification of detected candidates.
methods that rely predominantly on re-alignment strategies often contain a large number of false detected indels.
we used a nonconservative re-alignment strategy  to enrich the number of candidates and applied a discriminative machine learning-based approach to then classify indel candidates into true and false ones.
we achieved a classification accuracy of  <dig> % ±  <dig> % for deletions and  <dig> % ±  <dig> % for insertions.
furthermore, we showed that indel classification reduces the number of false candidates significantly and that missing classification may lead to spurious biological interpretations such as false frame shifts or gene losses.

 the detection of genetic variation between individuals is a key challenge in current research in genome biology. this variation includes single nucleotide polymorphisms, structural variants and copy number variants such as deletions, insertions or duplications, as well as copy number invariant changes like translocations or inversions. snps are used extensively to link phenotypic traits with associated genotypes in genome-wide association studies and to infer relationships in evolutionary studies. svs can provide additional insights into the genomic causes of phenotypic diversity. moreover, it is assumed that the total number of nucleotides spanned by svs greatly exceeds that of snps in human and plants. hence svs will be included more and more into these studies. furthermore, svs are associated with different types of human diseases and plant phenotypes. compared to snp identification, the detection of larger divergent sequences remains a challenging task. we here present a machine learning approach to predict svs based on ngs. traditionally, structural variants, in particular deletions and duplications, have been identified using array-based technologies, but these strategies suffered from a limited size and localization resolution, which is dependent on the density of probes or known markers. with the advent of ngs methods, whole-genome studies became feasible. small insertions and deletions up to a few base pairs in length were called by sensitive alignment tools in the routine re-sequencing process. however, the detection of larger structural variants based on depth-of-coverage or paired-end mapping methods could not reduce the sv size and localization resolution to the one base pair level. doc algorithms detect regions with absent or significantly elevated coverage, but are not able to determine the exact insertion location on the base pair level of the duplicated sequence. pem methods exploit the fact that the distance between the alignment locations of read pairs on a reference genome usually follow a normal distribution. clusters of read pairs mapping to the same genomic regions, whose distance is much shorter than expected can be explained by an insertion in the newly sequenced individual compared to the reference genome. the standard deviation and the mean of the insert size distribution define the sensitivity of this method. recently, so-called split-read mapping approaches were introduced to pinpoint structural variants and especially indels in the genome correctly to the base pair level. these methods use mapped-unmapped read pairs from a paired-end alignment performed by existing short read mapping tools. the mapped partner serves as anchor to realign the unmapped partner using alignment algorithms allowing for long-range gaps in both the reference sequence or the read. we will refer to the initial mapping which identifies murs as first and the split read alignment as second mapping pass throughout this manuscript. deletions up to a few tens or hundreds of base pairs in length can be identified by array based, doc and pem approaches, while conventional short read alignments are designed to find only deletions of a few base pairs. in contrast, srm predictions can in principle span the whole range of deletion lengths. however, the size of insertions is limited, and spurious alignments of the indel-flanking read parts might lead to multiple contradicting indel candidates. both limitations directly depend on the read length and are thought to be counterbalanced by longer sequences from advanced technologies. finally, deletions can be identified by limited de novo assembly methods, but they are not yet used routinely and require whole-genome alignments or close relative genomes for comparisons. though a large number of software packages for indel prediction from ngs data have been developed, application of these methods to identical data sets reveals little overlap. this is caused by different indel identification strategies. to reduce the number of false positive indel candidates, srm methods, such as pindel, rely on conservative realignment strategies. here, solely perfect and uniquely mapped reads are considered for further analysis. moreover, the realignment of the unmapped partner has to be mismatch-free as well. these constraints reduce the set of possible indel candidates drastically. existing srm programs report an indel as soon as two independent reads support the same sv, and if their partner reads lie within concordant insert sizes. other methods use several alignment features as evidence of an indel. however, either relying on logical rules or on generative probabilistic models, they require an empirically defined threshold, above which a candidate is a true sv. the most reliable way to verify indels is by capillary sequencing, but this is unfeasible for a genome-wide scan. thus, to identify a comprehensive set of indels, a non-conservative mapping strategy is needed that takes non-unique and non-perfect mapping reads into account. furthermore, to rate their trustworthiness, an evaluation method is needed which collects information about numerous alignment features from different approaches and automatically weighs their contributions. here we introduce an extended realignment split read strategy to identify a comprehensive set of indel candidates. a de novo machine learning method is applied to discriminate between ‘true’ and ‘false’ indel candidates based on more than alignment features, which can be derived from any short read mapping tool. its core is a support vector machine, a discriminative classifier that is trained on diverse alignment information on indel examples validated by reliable sanger sequencing. our svm approach avoids the step of defining thresholds for each feature by automatically learning them from sanger validated training data. we show that a commonly used criterion, namely the number of split read pairs supporting the same indel, is not sufficient to distinguish true indels from false candidates, but that additional features can accurately predict bona fide svs. concomitantly, our method reports the contribution of each feature to this decision process. our approach was applied to genomes of arabidopsis thaliana and its validity demonstrated by recovering a highly similar population structure of the analyzed strains solely based on positively classified indels compared to taking snp data as a basis.  indel candidate detection we performed a custom split read alignment method to retrieve indel candidates from the arabidopsis thaliana strain ice from phase i of the genomes project. the read lengths ranged from to bp with an average sequencing depth of 21x. all mapped-unmapped read pairs were retrieved from the available alignments from cao et al., which allowed base pair differences between read and reference, of which at most could be gaps. the mapped partner may have multiple alignment positions across the whole genome. because of many ambiguous alignments due to the high repetitivity of centromeric sequences, all murs within centromeres were excluded. the unmapped partners of the murs were mapped against col- in a bp window downstream of the mapped partner using gotoh’s alignment algorithm, allowing for long-range gaps as well as additional snps or few base pair-sized indels. all best-scoring alignments were reported and indels with a minimum support of two reads constituted the indel candidate set to be further evaluated. feature selection the split read alignment approach identified potential indel candidates for the arabidopsis thaliana strain ice we randomly selected deletion and insertion candidates across all chromosomes from this set and labeled them as true or false after sanger sequencing. thus, we retrieved two training sets. the training corpus for deletions consisted of correctly and falsely labeled examples and the training corpus for insertions of true and false ones. these sets were used to train a svm. pindel uses the number of split-read alignments supporting an indel with identical genomic coordinates as the only evidence for an indel. in a first study, only this alignment feature was used for classification. the f1-based training was contrasted to the use of several alignment characteristics, for insertions and for deletions. these features can be grouped into four main categories. the first considers the number of uniquely mapped reads and non-uniquely mapped reads overlapping the sequence space within a deletion. since this is not determinable for insertion signatures, this feature is only available for deletions. the second group comprises the number of umrs and n-umrs bp downstream as well as bp upstream of the indel candidate to represent the coverages to the right and left where bp reflects approximately the maximum read length. a ‘true’ deletion should show either zero or a low number of umrs within the deleted region compared to the umr-coverage up- and downstream thereof, whereas a certain number of n-umrs might be tolerated. the third group of features examines the concordance of snp and short indel calls detected by the two mapping passes. since these variations are compared to each other position-wise, short indels are considered as consecutive single position variants. these features can be interpreted as a check if the aligned reads of the first mapping pass in the vicinity of an indel derive from the same haplotype as the split reads spanning the indel. the last category includes general attributes such as the indel length and the split read alignment support of identically-located indels. discriminative training we trained a svm using a simple-to-interpret linear kernel on all three sets of features performing a 10-fold cross-validation for deletions and a 5-fold cross-validation for insertions and repeated each cross-validation times. the resulting average area under the receiver operating characteristic curves and average specificity-sensitivity-break-even-points suggest that the f1-based classification did not notably exceed the performance of a random guess for deletions and performs slightly better for insertions, whereas the use of and features reveal high concordance with the true classification. the training of the svm based on a linear kernel enabled us to identify the contributions of each feature to an indel prediction. positive weights contribute to the support, and negative to the rejection of a candidate. interestingly, the criteria for deletions and insertions notably differ from each other. while the strongest argument in favor for deletions is the number of sv supporting reads, it is the sequence length for insertions. furthermore, the agreement of spvs between the first and the second mapping pass contributes more to the acceptance of insertions, but is used as an indication against the trustworthiness of deletions. this effect might be explained by alignment errors by the first mapping pass close to deletions causing false positive spv calls. our classifier for insertions is trained on a dataset including true insertions. due to the limited size of this training dataset, it is to be expected that larger training datasets will further improve the prediction performance. indel prediction applying our machine learning approach with the f13/f feature set to indel candidates of strain ice positively classified out of deletions in total, and from insertions, respectively. the length of deletions ranged from to bp with a mean of bp and a median of bp. for insertions the length ranged from to bp with a mean and median of bp. thus, the svm was capable to extract information from the defined features leading to falsifications of indel candidates. ’false’ svs can be attributed to spurious mappings dependent on the length of the split read fragments or to multiple best-scoring alignments across the reference. next, we compared our predictions of indels in the strain ice to those identified by two versions of pindel. the minimum length of deletions was set to bp for all three sets, and the maximum deletion size constituted bp due to the adjustable restriction of the alignment space. pindel detected a total of and deletions larger than bp. % of pindel’s deletions were shared among all unclassified deletions of our approach. the svm classification identified and false positive deletions among the pindel candidates. further, our gotoh approach detected an additional set of and positively classified deletions. this can be explained by different mapping strategies. pindel in version requires uniquely and error-free mapped reads and allows only split read alignments where the read partners are aligned within two times the average insertion size. on the contrary, our svm approach follows a less conservative re-alignment strategy by analyzing non error-free and multiple best-scoring alignments of the same read. moreover, we tolerated split read mappings anywhere within the alignment window, which results in a larger candidate set by allowing the detection of svs in highly divergent regions. the subsequent classification compensates for these introduced levels of uncertainty. indeed, sanger sequencing revealed deletions, where the read partners showed discordant insert sizes. furthermore, a 61bp deletion, which was included in the training set and falsified by sanger sequencing, was reported by pindel, but correctly classified as false by our svm. this deletion would have proposed a potential frameshift in a coding region. due to general alignment restrictions, detecting insertions is limited in terms of their length. aligning a short sequence against a long one by introducing a series of gaps into the long sequence at the same time leads necessarily to an inferior alignment score. thus, pindel and our approach share merely 15% of all insertions. abyzov et al. investigated exactly this problem and proposed an improved alignment algorithm called age. applying this algorithm we could increase the number of shared insertions to 35%. indel detection and prediction on genomes next, we detected and classified indels in accessions of arabidopsis thaliana from the first phase of the genomes project. the average coverage of strains was 17x. by using a bp alignment window, on average ∼ positive deletions and ∼ positive insertions were reported per strain, the largest being bp long. combining similarly localized indels of identical length in different strains revealed non-redundant deletions and insertions in this population. altogether, they span over mb in total. almost half, ∼44%, were shared among more than one strain. we found long-range deletions spanning at least one complete gene sequence of the tair annotation with an average allele frequency of ∼. of those deletions were classified as whole gene losses if there was no unique read coverage within the deletion and sufficient coverage in the same-sized flanking regions, as determined by the first mapping pass. their average allele frequency was ∼. spurious read mapping within the deletion, ambiguous split read alignments, gene translocations or heterozygous deletions could explain long-range deletions not meeting the aforementioned criteria. as expected, only a minority of indels overlap with coding regions and have a potential deleterious effect on proteins. indels that do not alter the open reading frame of a gene outnumber those that do by almost two to one. however, the prediction of amino acid or framshift changes has been performed for each sv separately without considering potential nearby svs. it is known that additional nearby variants can compensate for frameshifts, thus the number of protein-changing svs reported here might still be an overestimate. population structure to further assess our method, we attempted to recover the population structure of the genomes with the predicted indels. to this end, three principal component analyses were performed: pca1) on our positively classified, non-private indels, pca2) on the non-private indels identified by the program pindel, and pca3) on the non-private indels identified by the program pindel. pca can successfully reconstruct the population structure, even slightly more distinctive as a pca with non-private snps. the first principal component distinguished the western and middle european accessions from the caucasian and russian individuals, explaining a variance of 20%. the second principle component with a variance of 6% was – as in cao et al. – not completely aligned with the latitude of the accessions. interestingly, the outlier yeg- from the caucasus found by cao et al. was positioned near the south russian and east asian cluster in our analysis as well. pca and pca revealed that the reported indels of the program pindel contain less information about population structure compared to our method. furthermore, the clustering of the subpopulations in pca is much more differentiable as in pca and pca the larger set of indels due to the more non-conservative re-alignment strategy and the removal of false indels seem to reflect the population structure more clearly, suggesting low rates of both false positives and false negatives. discussion we present a discriminative machine learning-based approach for detecting true structural variants among indel candidates. the key benefit of using a discriminative model is to learn to distinguish between true and false candidates based on a sanger validated ground truth, thereby reducing the false positive rate among predicted indels. we use our method on indel candidates generated via an exact gotoh re-alignment of paired-end reads, for which one partner could not be mapped. by considering multiply mapped reads on the whole genome and non-error free reads as well as accepting all mappings within the entire alignment window we receive a larger set of potential indel candidates. consequently, this non-conservative proceeding increases the chances for finding more true positives, but on the other hand tends to identify more false positives as well. due to that fact it is essential to accurately classify indel candidates using our machine learning approach. conceptually, our machine learning approach for true indel detection can be combined with any kind of alignment strategy and candidate generation scheme. indeed, to be able to detect more insertions a different alignment method can be useful. with the gotoh approach, shorter insertions are preferentially called than longer insertions in a pairwise alignment due to the reduced number of nucleotide matches the longer the insertion is. abyzov et al. developed an alignment tool called age to better call long insertions. their method was used on the ice genome in our framework and improved the overlap of insertions between pindel and the gotoh approach from 15% to 35%. current methods for indel scoring, which either rely on logical rules or generative probabilistic models, have to manually define a threshold above which candidates are predicted to be true structural variants. our machine learning approach avoids this step by automatically learning the threshold from the sanger validated training data. furthermore, all non-discriminative methods for scoring indel candidates have to solve the difficult task of how to weight different types of evidence for the occurrence of an indel. unlike these methods, our discriminative approach automatically learns the weights of different features. in addition, the automatic weighting of features indicates which features are relevant and which ones are less relevant for indel detection. from our results, we can confirm that our discriminative indel detection benefits from combining several features. the features we selected contain information that can reliably distinguish between true indels and false candidates as demonstrated by the consistent reconstruction of population structure based on true predicted indels. furthermore, we showed that tools not relying upon a classification step may lead to spurious biological interpretations. here, pindel identified a deletion candidate causing a potential frameshift, which our post-classification method predicted to be a false one; this prediction was confirmed by one of the sanger sequences. the classifier was trained on a corpus of reads from a paired-end library sequenced to 21-fold coverage. our method is robust to changes in fold coverage if the features that are derived from the read alignments, scale linearly with or are independent of sequencing depth. it is expected, that longer reads will improve our strategy since the longer the indel-flanking read sequences the less ambiguous split read alignments will be retrieved. the feature normalization we perform accounts for this fold change. to apply our method in different species, one would need to create a new sanger validated dataset to account for its particular genomic properties such as the degree of heterozygosity or repetitiveness. however, to circumvent laborious sanger sequencing, the increasing number of de novo assembled genomes or structural variant databases could serve as an alternative and extensive ground truth in future studies. the software, sanger validated training data and all annotated indels for the genomes are available at http://agkb.is.tuebingen.mpg.de/forschung/sv-m/.  we showed that accurate indel detection consists of two steps – the realignment of unmapped reads and the post-classification of detected candidates. methods that rely predominantly on re-alignment strategies often contain a large number of false detected indels. we used a nonconservative re-alignment strategy to enrich the number of candidates and applied a discriminative machine learning-based approach to then classify indel candidates into true and false ones. we achieved a classification accuracy of % ± % for deletions and % ± % for insertions. furthermore, we showed that indel classification reduces the number of false candidates significantly and that missing classification may lead to spurious biological interpretations such as false frame shifts or gene losses. 
as a consequence, structural variants detected in this manner contain many false positives. current methods for indel calling assign scores to different types of evidence or counter-evidence for the presence of an indel, such as the number of split read alignments spanning the boundaries of a deletion candidate or reads that map within a putative deletion. one of the major open challenges in next generation sequencing is the accurate identification of structural variants such as insertions and deletions. candidates with a score above a manually defined threshold are then predicted to be true indels. here, we present a machine learning based method which is able to discover and distinguish true from false indel candidates in order to reduce the false positive rate. we demonstrate the usefulness of our method with paired-end illumina reads from genomes of the first phase of the genomes project in arabidopsis thaliana. our method identifies indel candidates using a discriminative classifier based on features of split read alignment profiles and trained on true and false indel candidates that were validated by sanger sequencing. we demonstrate that missing classification may lead to spurious biological interpretations.
 one of the major open challenges in next generation sequencing is the accurate identification of structural variants such as insertions and deletions. current methods for indel calling assign scores to different types of evidence or counter-evidence for the presence of an indel, such as the number of split read alignments spanning the boundaries of a deletion candidate or reads that map within a putative deletion. candidates with a score above a manually defined threshold are then predicted to be true indels. as a consequence, structural variants detected in this manner contain many false positives.  here, we present a machine learning based method which is able to discover and distinguish true from false indel candidates in order to reduce the false positive rate. our method identifies indel candidates using a discriminative classifier based on features of split read alignment profiles and trained on true and false indel candidates that were validated by sanger sequencing. we demonstrate the usefulness of our method with paired-end illumina reads from genomes of the first phase of the genomes project in arabidopsis thaliana.  in this work we show that indel classification is a necessary step to reduce the number of false positive candidates. we demonstrate that missing classification may lead to spurious biological interpretations. the software is available at: http://agkb.is.tuebingen.mpg.de/forschung/sv-m/. next generation sequencingindel detectiondiscriminative machine learningpaired-end short readssplit-read mapping 