A Boolean algebra for genetic variants

Abstract

Motivation: Beyond identifying genetic variants, we introduce a set of Boolean relations, which allows for a comprehensive classification of the relations of every pair of variants by taking all minimal alignments into account. We present an efficient algorithm to compute these relations, including a novel way of efficiently computing all minimal alignments within the best theoretical complexity bounds.

Results: We show that these relations are common, and many non-trivial, for variants of the CFTR gene in dbSNP. Ultimately, we present an approach for the storing and indexing of variants in the context of a database that enables efficient querying for all these relations.

Availability and implementation: A Python implementation is available at https://github.com/mutalyzer/algebra/tree/v0.2.0 as well as an interface at https://mutalyzer.nl/algebra.

Fig. 1.

The top panel shows alignments for two variants, GATCCTG and GATCTG, with the same reference sequence GAATCG, where the changes (*common to both, ^†unique for one of them) suggest overlap. The bottom panel shows these same variants, but now obtained through different alignments, where the changes this time suggest that the left variant contains the right one

Fig. 2.

Computation matrix of the simple edit distance between $R=\mathtt{CATATATCG}$ and $O=\mathtt{CTTATAGCAT}$. Matching symbols are annotated with a circle. The highlighted path shows one of the minimal alignments

Fig. 3.

Computing the elements of Equation (4) for $R=\mathtt{CATATATCG}$ and $O=\mathtt{CTTATAGCAT}$ to efficiently reconstruct the set of all minimal variant representations. (a) Expanded elements for f = 1 with $\mathrm{rows}=[1,2]$ and $\mathrm{cols}=[0,1,1]$. (b) Expanded elements for f = 3 with $\mathrm{rows}=[2,3,4,5, 6,6,7]$ and $\mathrm{cols}=[1,2,3,3,4,5,6,6]$. (c) Expanded elements for f = 5 with $\mathrm{rows}=[3,4,5,6, 7,7,8,8,9]$ and $\mathrm{cols}=[2,3,4,5,6,7,7,7,8,8]$. (d) Expanded elements for f = 7 with $\mathrm{rows}=[4,5,6,7, 8,8,9,10,10,10]$ and $\mathrm{cols}=[3,4,5,6,7,8,8,9,9,9,9]$

Fig. 4.

The LCS-graph for $R=\mathtt{CATATATCG}$ and $O=\mathtt{CTTATAGCAT}$. The coordinates refer to the coordinates of the matching symbols in Figure 3. Unlabeled edges indicate consecutive matches and do not contribute to the set of elements of all minimal variant representations

Fig. 5.

Scatterplot of the average number of non-disjoint relations of all variants in CFTR with a certain maximal influence interval length

Fig. 6.

The distribution of the number of non-disjoint relations per variant. The long tail of counts of 11 and above are aggregated. The most relations a single variant has is 435