HAllA (Hierarchical All-against-All association) is a tool to find multi-resolution associations in high-dimensional, heterogeneous datasets. For a pair of datasets containing measurements that describe the same set of samples, Hierarchical All-against-All Association (HAllA) testing proceeds by 1) discretizing features to a uniform representation, 2) hierarchically clustering each dataset separately to generate two data hierarchies, 3) coupling clusters of equivalent resolution between the two data hierarchies, and 4) iteratively testing coupled clusters of increasing resolution for statistically significant association.
HAllA inputs. Data in scientific studies often come paired in the form of two high-dimensional datasets, where the dataset X (with p features/rows and n samples/columns) are assumed to be p predictor variables (or features) measured on n samples that give rise to d response variables contained in the dataset Y (with d features/rows and n samples/columns). Note that column i of X is sampled jointly with column i of Y, so that X and Y are aligned.
HAllA output. HAllA reports significant associations between clusters of related features. Each association is characterized by a cluster from the first dataset, a cluster from the second dataset, and measures of statistical significance and the effect size of the association between the clusters (by p-value, q-value, and similarity score.
- Please direct questions to the HAllA Google Group ( email@example.com ) and subscribe to receive HAllA news.
- For additional information, see the HAllA User Manual.
- How to run
- Visualizing HAllA results
- HAllA extensions
$ brew tap biobakery/biobakery $ brew install halla
This will also install all HAllA dependencies.
You can install HAllA automatically with pip.
$ pip install halla
This will install the latest version of HAllA and all its dependencies.
Alternatively, you can manually install HAllA from source and then manually install the dependencies.
Step 1: Download HAllA and unpack the software:
$ tar xzvf biobakery-halla-<versionid>.tar.gz $ cd biobakery-halla-<versionid>/
Step 2: Install HAllA:
$ python setup.py install
Add the --user option if you do not have root install permissions.
Step 3: Install the HAllA dependencies.
HAllA requires as input two tab-delimited text files representing two paired datasets describing the same set of samples. Download the set of two files to get started on the tutorial (click on the link then right-click on the "Save as..." option on the preview page to download the files).
These two files contain 16 normally-distributed features for 100 samples (all synthetic data). Cluster structure was spiked into each dataset, and some clusters were forced to be associated (for demonstration purposes).
Next, run HAllA on the two demo input files, placing the output files in your current working directory under synthetic_output:
$ halla -X X_16_100.txt -Y Y_16_100.txt --output synthetic_output -m spearman
The "-m" option is used to request a measure of similarity between features. This measure is used both for identifying clusters within each dataset, as well as to identify associations between clusters. Here, "spearman" indicates Spearman's rank correlation. If you would like to run with multiple cores, add the option --nproc. The --fdr option can be used to define the false discovery rate (FDR) procedure. "bh" refers to Benjamini-Hochberg FDR correction.
The command above creates three primary output files, which can also be downloaded from the links below:
Let's examine these files individually, starting with associations.txt:
$ less -S synthetic_output/associations.txt
association_rank cluster1 cluster1_similarity_score cluster2 cluster2_similarity_score pvalue qvalue similarity_score_between_clusters 1 X12;X13 0.73301320528211289 Y12;Y13 0.74434573829531803 0.0 0.0 0.84086434573829538 2 X14;X15 0.76941176470588246 Y14;Y15 0.65138055222088831 1.3073481596959805e-19 9.4129067498110597e-19 0.82588235294117651 3 X9;X10;X11 0.61162064825930362 Y9;Y10;Y11 0.7375270108043217 0.0 0.0 0.79140456182472985 4 X6;X7;X8 0.72830732292917166 Y6;Y7;Y8 0.64638655462184869 1.4285081274091766e-07 8.57104876445506e-07 0.6298679471788714 5 X0;X1;X2 0.70861944777911168 Y0;Y1;Y2 0.6923889555822329 0.0 0.0 0.61767106842737096 6 X3;X4;X5 0.64427370948379348 Y3;Y4;Y5 0.74597839135654265 0.0 0.0 0.60038415366146469 7 X15 1.0 Y6 1.0 0.00028074428246968331 0.0087431790826272802 0.49253301320528209
This file reports associations between clusters, as described above.
Now let's examine similarity_table.txt:
$ less -S synthetic_output/similarity_table.txt
# Y0 Y1 Y2 Y12 Y13 Y14 Y15 Y6 Y7 Y8 Y3 Y4 Y5 Y9 Y10 Y11 X9 -0.298 -0.105 -0.141 0.122 -0.085 0.028 -0.134 -0.161 -0.043 -0.064 0.312 0.341 0.357 0.574 0.403 0.245 X10 -0.186 -0.033 0.004 0.098 -0.087 0.038 -0.097 -0.032 -0.078 -0.006 -0.008 0.051 0.052 0.551 0.791 0.638 X11 -0.109 0.045 0.025 0.065 -0.009 0.008 -0.072 -0.037 0.028 0.084 0.096 0.092 -0.030 0.381 0.559 0.708 X0 0.759 0.475 0.164 -0.315 -0.124 -0.205 -0.192 -0.033 -0.253 0.005 0.129 0.181 0.180 -0.069 -0.129 0.018 X1 0.486 0.618 0.250 0.008 -0.037 -0.259 -0.221 -0.081 -0.097 -0.049 0.284 0.238 0.283 0.150 0.058 0.204 X2 0.522 0.558 0.535 0.030 0.079 -0.088 -0.031 -0.020 -0.070 0.016 0.111 0.064 0.122 0.076 0.020 0.168 X3 0.048 0.034 0.012 -0.057 -0.187 -0.032 -0.189 -0.128 -0.074 0.058 0.637 0.433 0.342 0.101 0.036 0.009 X4 0.219 0.184 0.050 0.046 0.026 0.152 0.045 0.058 -0.064 0.118 0.477 0.600 0.549 0.216 0.144 0.093 X5 0.289 0.341 0.219 0.116 0.063 0.146 0.154 0.209 0.121 0.224 0.309 0.424 0.634 0.294 0.144 0.148 X12 -0.101 -0.009 0.081 0.851 0.614 0.027 -0.154 0.008 -0.062 -0.226 0.195 0.093 0.179 0.260 0.214 0.132 X13 0.021 0.038 0.160 0.660 0.841 0.266 0.061 -0.021 -0.048 -0.196 0.033 -0.020 0.093 0.212 0.096 0.065 X14 0.013 -0.093 -0.015 0.084 0.361 0.815 0.611 0.390 0.143 0.077 -0.333 -0.199 -0.169 0.033 -0.073 -0.103 X15 -0.086 -0.140 -0.175 0.067 0.258 0.581 0.826 0.493 0.316 0.304 -0.287 -0.109 0.014 -0.020 -0.110 -0.146 X6 -0.076 -0.016 -0.048 -0.008 0.011 0.295 0.278 0.659 0.511 0.291 -0.390 -0.099 -0.089 0.136 0.027 -0.011 X7 -0.082 0.064 -0.023 -0.091 -0.016 0.046 0.149 0.385 0.630 0.327 -0.313 -0.100 -0.019 0.228 0.038 0.085 X8 -0.054 0.023 0.006 -0.138 -0.095 0.015 0.205 0.269 0.548 0.544 -0.344 -0.163 -0.049 0.065 0.059 0.104
This file contains pairwise similarity scores for all pairs of features from the first dataset and the second dataset.
Option --write-hypothesis-tree can be used to write hypothesis tree with the halla command. The hypothesis tree will be in the hypotheses_tree.txt file:
$ less -S synthetic_output/hypotheses_tree.txt
Level Dataset 1 Dataset 2 0 X9;X10;X11;X0;X1;X2;X3;X4;X5;X12;X13;X14;X15;X6;X7;X8 Y0;Y1;Y2;Y12;Y13;Y14;Y15;Y6;Y7;Y8;Y3;Y4;Y5;Y9;Y10;Y11 1 X9;X10;X11 Y0;Y1;Y2 1 X9;X10;X11 Y12;Y13 1 X9;X10;X11 Y9;Y10;Y11 1 X9;X10;X11 Y3;Y4;Y5 1 X9;X10;X11 Y6;Y7;Y8 1 X9;X10;X11 Y14;Y15 1 X12;X13 Y0;Y1;Y2 1 X12;X13 Y12;Y13 1 X12;X13 Y9;Y10;Y11 1 X12;X13 Y3;Y4;Y5 1 X12;X13 Y6;Y7;Y8 1 X12;X13 Y14;Y15 1 X3;X4;X5 Y0;Y1;Y2 1 X3;X4;X5 Y12;Y13 1 X3;X4;X5 Y9;Y10;Y11 1 X3;X4;X5 Y3;Y4;Y5 1 X3;X4;X5 Y6;Y7;Y8 1 X3;X4;X5 Y14;Y15 1 X0;X1;X2 Y0;Y1;Y2 1 X0;X1;X2 Y12;Y13 1 X0;X1;X2 Y9;Y10;Y11 1 X0;X1;X2 Y3;Y4;Y5 1 X0;X1;X2 Y6;Y7;Y8 1 X0;X1;X2 Y14;Y15 1 X6;X7;X8 Y0;Y1;Y2 1 X6;X7;X8 Y12;Y13 1 X6;X7;X8 Y9;Y10;Y11 1 X6;X7;X8 Y3;Y4;Y5 1 X6;X7;X8 Y6;Y7;Y8 1 X6;X7;X8 Y14;Y15 1 X14;X15 Y0;Y1;Y2 1 X14;X15 Y12;Y13 1 X14;X15 Y9;Y10;Y11 1 X14;X15 Y3;Y4;Y5 1 X14;X15 Y6;Y7;Y8 1 X14;X15 Y14;Y15 2 X9 Y0 2 X9 Y2 2 X9 Y1 2 X11 Y0 2 X11 Y2 2 X11 Y1 2 X10 Y0 2 X10 Y2 2 X10 Y1
This file contains a comprehensive report of all testing performed during the HAllA run (not limited to the significant associations reported in associations.txt. Level zero hold all the features in HAllA starts performing tests from level 1.
- What is the pairwise similarity score between feature X9 and feature Y11 in association number 3? How does this score compare the similarity score given for association number 3?
- What is the pairwise similarity score between X15 and Y6? How does this compare to the strength of association considered above? How is this difference reflected in the *p*-value and *q*-value of the test for these two features?
Here we will consider subsets of a published dataset (Morgan et al., Genome Biology 2015) that combined 1) 16S rRNA amplicon sequencing of the human gut microbiome (64 taxa) and 2) Affymetrix microarray screens of colonic RNA expression across 204 patients with ulcerative colitis (100 genes). We will refer to this as the "pouchitis dataset." The purpose of this study was to associate human genes and microbial taxa with the recurrence of inflammation following ileal resection surgery (a surgical procedure in ulcerative colitis that involves removing of the large intestine and rectum and attaching the lowest part of the small intestine to a hole made in the abdominal wall to allow waste to leave the body).
Download the paired, subsampled OTU-gene datasets:
Run HAllA on these datasets:
$ halla -X OTU_64.txt -Y Gene_100.txt -o pouchitis_output -m spearman --header -q 0.25
Note the addition of the "-q" flag: this flag defines the target FDR, here 0.25, i.e. the expected fraction of false positive reports among returned significant associations. --header uses the header of the two datasets to find common columns (samples) and reorder them.
The output files generated from the command above can be downloaded from the following links:
Inspect these files as we did above the synthetic example.
hallagram is a tool included with HAllA for visualizing the three output files we looked at in text-form above. Run hallagram as follows (use hallagram -h for help with plot options):
$ cd synthetic_output $ hallagram similarity_table.txt hypotheses_tree.txt associations.txt --outfile hallagram.png
Please open the file hallagram_strongest_7.png, which should look like this:
- How many features are involved in the largest association in the figure? How many pairwise associations does this cluster association represent? Does it appear as though the pairwise associations are reasonably homogeneous in terms of their strength?
- Are there any pairs of clusters with a significant negative association?
- Do you think that HAllA's approach improved statistical power in this scenario? How would power be different if all X and Y features were compared individually?
Let's try some of the other hallagram options using the pouchitis dataset (gut OTUs and host gene expression):
$ cd pouchitis_output $ hallagram similarity_table.txt hypotheses_tree.txt associations.txt --outfile hallagram.pdf --outfile hallagram.png --similarity Spearman --axlabels "Macrobial OTUs" "Host transcipts" --strongest 50
- --similarity option names the similarity methods has been used in this analysis in the legend.
- --axlabels option add X-axis label and Y-axis label.
- --strongest 50 option to used 50strongest associations order by similarity score(--order-by can be used to use pvalue or qvalue for order instead of similarity score.
- How would you interpret association number 32?
- How would your answers regarding the previous hallagram change here?
HAllA uses a hierarchical approach for blockwise association testing between clusters in different levels in hierarchies. Naive all-aginst-all (AllA), pairwise, association testing can be used by -a AllA. The default is -a HAllA. Let's try AllA approach on the synthetic data:
$ halla -X X_16_100.txt -Y Y_16_100.txt --output synthetic_output_alla -m spearman -a AllA
- What has changed in the output files?
HAllA is extensible to similarity metrics. By default, HAllA uses normalized mutual information (NMI) and discretizes datasets to use NMI. We recommend using Spearman coefficient if all data are continuous, with a small number of samples, and looking for monotonic associations. Adjusted mutual information (AMI), maximum information coefficient (MIC), Pearson, distance correlation (dcor), and discretized maximum information coefficient (DMIC) are the other similarity metrics that currently are implemented in HAllA. A similarity metric is used to build hierarchical clusters and also to be used in permutation test in HAllA. -m $SIMILARTITY_METRIC is the option to be used with HAllA command line. Let's try dcor as similarity metric:
$ halla -X X_16_100.txt -Y Y_16_100.txt --output synthetic_output_dcor -m dcor
- What has changed in the output files?
Benjamini–Hochberg(BH) as default, Benjamini–Yekutieli (BY), and Bonferroni are implemented as multiple test correction methods in HAllA. BH is used as the default in HAllA and can be changed by --fdr option. Let's try bonferroni:
$ halla -X X_16_100.txt -Y Y_16_100.txt --output synthetic_output_bonferroni -m spearman --fdr bonferroni
- What has changed in the output files?
- How the results change in AllA case with bonferroni?
Medoid of a cluster is used as a representative to participate in association testing. Decomposition methods such as principal component analysis (PCA), multiple correspondence analysis analysis (MCA), independent component analysis (ICA).PCA and ICA can be used only with continue data and when looking for monotonic relations. With PCA or ICA, the first component will be used as the representative of a cluster. MCA can be used with both categorical and continuous data. Let's try pca:
$ halla -X X_16_100.txt -Y Y_16_100.txt --output synthetic_output_pca -m spearman -d pca