ann-linkage-clustering 0.11.1

Linkage clustering via Approximate Nearest Neighbors

Find Co-Abundant Groups of Genes

Purpose

Analyze gene abundance data from a large set of samples and calculate which sets of genes are found at a similar abundance across all samples. Those genes are expected to be biologically linked, such as the case of metagenomic analysis via whole-genome shotgun sequences, where genes from the same genome tend to be found at a similar abundance.

Code Availability

The code in this repository is provided in two different formats. There is a library of Python code (ann_linkage_clustering in PyPI) that can be used to make CAGs directly from a Pandas DataFrame. There is also a Docker image that is intended to be run with the script find-cags.py. The documentation below describes the end-to-end workflow that is available with that Docker image and the single wrapper script.

Input Data Format

It is assumed that all input data will be in JSON format (gzip optional). The pertinent data for each individual sample is an abundance metric for each sample. The input file must contain a list in which each element is a dict that contains the gene ID with one key and the abundance metric with another key.

For initial development we will assume that each input file is a single dict, with the results located at a single key within that dict. In the future we may end up supporting more flexibility in extracting results from files with different structures, but for the first pass we'll just go with this.

Therefore the features that must be specified by the user are:

• Key for the list of gene abundances within the JSON (e.g. "results")
• Key for the gene_id within each element of the list (e.g. "id")
• Key for the abundance metric within each element (e.g. "depth")

Here is an example of what that might look like in JSON format:

{
  "results": [
    {
      "id": "gene_1",
      "depth": 1.1
    },
    {
      "id": "gene_2",
      "depth": 0.2
    },
    {
      "id": "gene_3",
      "depth": 3000.015
    },
  ],
  "logs": [
    "any other data",
    "that you would like",
    "to include in this file is just fine."
  ]
}

NOTE: All abundance metric values must be >= 0

Running from any DataFrame

If you have any other format of data, you can use this code to find CAGs as well. The big difference is that this script does some data normalization that is very helpful. For example, if you are using cosine distance, it's best to have the value indicating absence to be zero. So if you are using the centered log-ratio (clr) normalization approach, you really need to set a standard cuttoff across all samples, trim the lowest value to that, and then set that lowest value to zero. This is all done automatically by find-cags.py, but you can absolutely use the same functions to make CAGs with any other input data format or normalization approach.

You can follow the workflow in the find-cags.py script, which basically follows this workflow (assuming that df is your DataFrame of abundance data, with genes in rows and samples in columns):

from multiprocessing import Pool
from ann_linkage_clustering.lib import make_cags_with_ann
from ann_linkage_clustering.lib import iteratively_refine_cags
from ann_linkage_clustering.lib import make_nmslib_index

# Maximum distance threshold (use any value)
max_dist=0.2

# Distance metric (only 'cosine' is supported)
distance_metric="cosine"

# Multiprocessing pool (pick any number of threads, in this case `1`)
threads = 1
pool = Pool(threads)

# Linkage type (only `average` is fully supported)
linkage_type = "average"

# Make the ANN index
index = make_nmslib_index(df)

# Make the CAGs in the first round
cags = make_cags_with_ann(
    index,
    max_dist,
    df,
    pool,
    threads=threads,
    distance_metric=distance_metric,
    linkage_type=linkage_type
)

# Iteratively refine the CAGs (this is the part that is hardedcoded to 
# use average linkage clustering, while the step above could technically
# use any of `complete`, `single`, `average`, etc.)
iteratively_refine_cags(
    cags,
    df.copy(),
    max_dist,
    distance_metric=distance_metric,
    linkage_type=linkage_type,
    threads=threads
)

At the end of all of that, the cags object is a dictionary containing all of the identified groups.

Sample Sheet

To link individual files with sample names, the user will specify a sample sheet, which is a JSON file formatted as a dict, with sample names as key and file locations as values.

Data Locations

At the moment we will support data found in either the local file system or AWS S3.

Test Dataset

For testing, I will use a set of JSONs which contain the abundance of individual genes for a set of microbiome samples. That data is found in the tests/ folder. There is also a JSON file indicating which sample goes with which file, which is formatted as a simple dict (keys are sample names and values are file locations) and located in tests/sample_sheet.json.

Normalization

The --normalize metric accepts three values, clr, median, and sum. In each case the abundance metric for each gene within each sample is divided by either the median or the sum of the abundance metrics for all genes within that sample. When calculating the median, only genes with non-zero abundances are considered. For clr, each value is divided by the geometric mean for the sample, and then the log10 is taken. All zero values are filled with the minimum value for the entire dataset (so that they are equal across samples, and not sensitive to sequencing depth).

Approximate Nearest Neighbor

The Approximate Nearest Neighbor algorithm as implemented by nmslib is being used to create the CAGs. This implementation has a high performance in an independent benchmark.

Distance Metric

The distance metric is now hard-coded to be the cosine similarity. This is limited by the available functionality of ANN in nmslib, and therefore has been standardized to the other parts of the codebase as well.

Refinements

After finding CAGs, the algorithm will iteratively join CAGs that are very similar to each other in aggregate. This increases the fidelity of the final CAGs and mitigates some of the sensitivity limitations of ANN.

Invocation

usage: find-cags.py [-h] --sample-sheet SAMPLE_SHEET --output-prefix
                    OUTPUT_PREFIX --output-folder OUTPUT_FOLDER
                    [--normalization NORMALIZATION] [--max-dist MAX_DIST]
                    [--temp-folder TEMP_FOLDER] [--results-key RESULTS_KEY]
                    [--abundance-key ABUNDANCE_KEY]
                    [--gene-id-key GENE_ID_KEY] [--threads THREADS]
                    [--min-samples MIN_SAMPLES] [--clr-floor CLR_FLOOR]
                    [--test]

Find a set of co-abundant genes

optional arguments:
  -h, --help            show this help message and exit
  --sample-sheet SAMPLE_SHEET
                        Location for sample sheet (.json[.gz]).
  --output-prefix OUTPUT_PREFIX
                        Prefix for output files.
  --output-folder OUTPUT_FOLDER
                        Folder to place results. (Supported: s3://, or local
                        path).
  --normalization NORMALIZATION
                        Normalization factor per-sample (median, sum, or clr).
  --max-dist MAX_DIST   Maximum cosine distance for clustering.
  --temp-folder TEMP_FOLDER
                        Folder for temporary files.
  --results-key RESULTS_KEY
                        Key identifying the list of gene abundances for each
                        sample JSON.
  --abundance-key ABUNDANCE_KEY
                        Key identifying the abundance value for each element
                        in the results list.
  --gene-id-key GENE_ID_KEY
                        Key identifying the gene ID for each element in the
                        results list.
  --threads THREADS     Number of threads to use.
  --min-samples MIN_SAMPLES
                        Filter genes by the number of samples they are found
                        in.
  --clr-floor CLR_FLOOR
                        Set a minimum CLR value, 'auto' will use the largest
                        minimum value.
  --test                Run in testing mode and only process a subset of 2,000
                        genes.