Source-linked AI summary
Jaccard/Tanimoto similarity test and estimation methods
Neo Christopher Chung, Błażej Miasojedow, Michał Startek, Anna Gambin
TL;DR
Statistical testing of Jaccard/Tanimoto similarity for binary presence-absence data has been limited despite its widespread use in co-occurrence analysis. The paper develops exact, asymptotic, bootstrap, and measure concentration methods, finding accurate significance estimates with estimation methods substantially faster than the exact solution. These methods are implemented for broad binary-data applications, while the exact approach remains computationally demanding for large datasets.
Problem
Jaccard/Tanimoto similarity is widely used for binary co-occurrence data, but its probabilistic interpretation, statistical testing, and p-value estimation have been inadequately studied.
Method
The paper derives a hypothesis test with occurrence-probability-aware centered coefficients, exact and asymptotic solutions, bootstrap estimation, and measure concentration algorithms.
Results
The proposed methods produce accurate p-values and false discovery rates, while bootstrap and measure concentration estimation are orders of magnitude faster than the exact solution.
Takeaways & Limitations
The methods provide a rigorous framework for identifying non-random co-occurrences and can be applied to binary data in genomics, biochemistry, and other sciences.
Takeaways & Limitations
Exact significance testing requires exhaustive computations, and the conventional coefficient is undefined when both binary vectors contain only zeros.
Abstract
from arXiv · showhide
Binary data are used in a broad area of biological sciences. Using binary presence-absence data, we can evaluate species co-occurrences that help elucidate relationships among organisms and environments. To summarize similarity between occurrences of species, we routinely use the Jaccard/Tanimoto coefficient, which is the ratio of their intersection to their union. It is natural, then, to identify statistically significant Jaccard/Tanimoto coefficients, which suggest non-random co-occurrences of species. However, statistical hypothesis testing using this similarity coefficient has been seldom used or studied. We introduce a hypothesis test for similarity for biological presence-absence data, using the Jaccard/Tanimoto coefficient. Several key improvements are presented including unbiased estimation of expectation and centered Jaccard/Tanimoto coefficients, that account for occurrence probabilities. We derived the exact and asymptotic solutions and developed the bootstrap and measurement concentration algorithms to compute statistical significance of binary similarity. Comprehensive simulation studies demonstrate that our proposed methods produce accurate p-values and false discovery rates. The proposed estimation methods are orders of magnitude faster than the exact solution. The proposed methods are implemented in an open source R package called jaccard (https://cran.r-project.org/package=jaccard). We introduce a suite of statistical methods for the Jaccard/Tanimoto similarity coefficient, that enable straightforward incorporation of probabilistic measures in analysis for species co-occurrences. Due to their generality, the proposed methods and implementations are applicable to a wide range of binary data arising from genomics, biochemistry, and other areas of science.
Background
The paper addresses limited statistical support for Jaccard/Tanimoto similarity in binary presence-absence data by introducing rigorous tests, estimation methods, and implementations for biological co-occurrence analysis.
- Jaccard/Tanimoto similarity compares binary presence-absence vectors through the ratio of their intersection to their union.
- Existing Jaccard/Tanimoto analyses lacked probabilistic interpretations, statistical error controls, and adequately studied p-value estimation methods.
- The proposed framework derives exact and asymptotic solutions and introduces efficient estimation methods for testing similarity significance.
- Simulation studies evaluate p-values and false discovery rates, while applications examine bird species on 28 Vanuatu islands and fish species across 3347 freshwater habitats in France.
- The methods are implemented in the R package jaccard and an interactive web app for testing similarity in binary data.
Statistical Model and Test
The statistical model represents species occurrences as independent Bernoulli vectors under the null hypothesis and uses the Jaccard/Tanimoto coefficient to test whether observed similarity departs from independence.
- The framework tests whether two presence-absence vectors are significantly related using their Jaccard/Tanimoto similarity coefficient.
- Under independence, each vector is modeled as i.i.d. Bernoulli data with occurrence probabilities p_i and p_j.
- The expected Jaccard/Tanimoto coefficient under independence is p_i p_j divided by p_i + p_j − p_i p_j.
- The four presence-absence outcome categories follow a multinomial distribution with m trials and probabilities determined by p_i and p_j.
- The centered coefficient compares observed similarity with its expected value, so negative and positive values correspond naturally to negative and positive associations.
- The null hypothesis sets the centered coefficient to zero, equivalently treating the conventional coefficient as equal to its independence expectation.
Distribution of the Jaccard/Tanimoto Coefficient
The paper derives exact and asymptotic null distributions for Jaccard/Tanimoto similarity, then estimates unknown occurrence probabilities while correcting plug-in bias for significance testing.
- The exact null distribution expresses Jaccard/Tanimoto similarity through multinomial counts but requires exhaustive computation.
- When occurrence probabilities are known, p-values are computed from the null distribution of the centered coefficient.
- The centered coefficient uses estimated occurrence probabilities to compare observed similarity with its estimated independence expectation.
- Same-sample plug-in expectations are biased toward observed similarity, so probabilities are estimated separately for each multinomial configuration.
- The asymptotic approximation applies as m →∞ and estimates variance using probabilities for joint presences and single-vector presences.
- Unknown occurrence probabilities are estimated from observed presence frequencies and substituted into the asymptotic quantities.
Measure Concentration Algorithm
The measure concentration algorithm estimates probabilities for centered Jaccard/Tanimoto similarity by focusing on a high-probability region of a multinomial distribution. It uses concentration around the mode to avoid exhaustive computation while retaining a known error bound.
- Motivation: The exact significance test requires summing over all possible multinomial states, making computation exhaustive.
- Performance: The measure concentration algorithm quickly and accurately estimates the required probability with a known error bound.
- Method: The algorithm constructs I_ε, a set of multinomial states whose total probability reaches at least 1 − ε.
- Method: Neighboring states differ by moving one element to a different multinomial class.
- Method: It begins at the multinomial mode and expands through neighboring states until the desired probability mass is covered.
Bootstrap Procedure
The bootstrap procedure estimates the null distribution of centered Jaccard/Tanimoto coefficients by independently resampling the two binary vectors. This provides flexible p-value estimation while breaking potential dependence between the vectors.
- Method: Independent resampling with replacement breaks potential dependency between the two presence-absence vectors.
- Implementation: The bootstrap algorithm takes two binary vectors as input and returns a p-value.
- Method: The procedure uses resampled vectors to estimate the expectation and generate an empirical null distribution of Jaccard/Tanimoto coefficients.
- Tuning: Larger B produces a more precise empirical null distribution and p-value estimate.
- Tuning: The simulations used B = 5×m, which the authors report as accurate and fast.
Simulation Studies
Simulation studies evaluated calibration, false discovery rates, computational efficiency, and competing co-occurrence methods. Exact, bootstrap, and measure concentration approaches produced accurate null p-values, while estimation methods were substantially faster than the exact solution.
- Null calibration: Exact, bootstrap (B = 500), and measure concentration algorithms followed Uniform(0,1) null p-value distributions across all simulated occurrence probabilities.
- Null calibration: Asymptotic p-values were anti-conservative for p = 0.3 and 0.5, slightly conservative for p = 0.7 and 0.9, and recommended only when time is critical.
- False discovery rates: False discovery rates were evaluated on mixtures of independent and dependent datasets with null proportions π0 = .25, .50, and .75.
- Computational efficiency: At m = 500, bootstrap was 449.8 times faster than the exact solution, while MCA was 92.5 times faster.
- Computational efficiency: The proposed computational methods showed increasingly greater efficiency gains over the exact solution as vector length increased.
- Comparative evaluation: The study also compared combinatorics and hypergeometric-distribution methods using independent presence-absence data.
Applications in Species Co-occurrences
The proposed Jaccard/Tanimoto tests were applied to bird and fish presence-absence data to identify statistically significant, non-random species co-occurrences. Bootstrap and measure concentration methods produced efficient significance estimates, while applications extended the framework across biological binary data.
- Bird species on Vanuatu islands: Three hundred seventy-four of 1,378 bird-species pairs were significant at q-value 0.10.The estimated proportion of independent species pairs was 24% using q-value methodology.
- Computational evaluation: Bootstrap and measure concentration estimates of bird-pair p-values were almost identical, with mean squared deviation 1.15 × 10^-4.The bootstrap used B = 5000, while measure concentration used accuracy 1 × 10^-5.
- Fish species in French freshwater streams: 84.3% of 496 fish-species pairs in French freshwater habitats were estimated to co-occur non-randomly.The data covered 32 common fish species across 3,347 sites surveyed from 1980 to 1991.
- Interpretation and scope: The framework identifies statistically significant deviations from random samples as non-random species co-occurrences.The methods provide exact, asymptotic, bootstrap, and measure concentration solutions for Jaccard/Tanimoto similarity testing.
- Broader applications: The implementations extend rigorous binary-similarity testing to genomics, biochemistry, and other biological applications.The methods are available through an open-source R package and a Shiny web app.
Figures
The figures evaluate the proposed Jaccard/Tanimoto methods through null-calibrated p-values, false-discovery control, computational runtime, and bird-species applications.
- Simulation calibration: Figure 2 evaluates four proposed methods using 2000 independent variables across occurrence probabilities p = .1, .3, .5, .7, .9.The diagonal lines represent theoretically correct Uniform(0,1) p-value distributions.
- False-discovery control: Figure 3 evaluates FDR estimates across null proportions π0 = .25, .50, .75 using 2000 presence-absence vectors and repeated simulations.Downward deviations from the diagonal indicate conservative behavior.
- Computational efficiency: Figure 4 compares mean runtimes of four proposed methods over dimensions m = 50, . . . , 500.Bootstrap and MCA become relatively more efficient than the exact solution as dimension increases.
- Centered similarity: Figure 5 shows that centering conventional coefficients by their independence expectations alleviates their dependence on those expectations.The comparison uses uncentered and centered coefficients from the bird dataset.
- Computational efficiency: Figure S1 extends runtime comparisons to m = 10000; the exact solution is impractical for m ≥1000, while asymptotic computation is instantaneous regardless of m.Bootstrap and MCA are orders of magnitude faster than the exact solution.
- Method agreement: Figure S6 finds minimal disagreement between bootstrap and MCA p-values across 1378 bird-species co-occurrences, with mean squared deviation 1.15 × 10−4.The diagonal red line indicates identity.