broadinstitute / catch / 370

94%

master: 94%

push

travis-ci-com

Make default clustering method be simple search for connected components

This commit adds `utils.cluster.find_connected_components()` to identify
connected components in a graph in which sequences are adjacent iff
their estimated distance is within a threshold. As with previous
clustering, distances with this method continue to be estimated using a
MinHash family, e.g., as in the Mash paper (Ondov et al. 2016).

The commit makes this method the default for clustering because it
should be less memory-intensive than the existing hierarchical approach
for large numbers of input sequences; it does not need to store a
pairwise distance matrix. It adds an argument to design.py to specify
the clustering method, so the hierarchical clustering method---which
appears to be faster---can still be used.

1756 of 1998 branches covered (87.89%)

90 of 90 new or added lines in 3 files covered. (100.0%)

5536 of 5862 relevant lines covered (94.44%)

1.89 hits per line