We used the method of [13] to identify maximal bicliques. We define a biclique as a set of polymorphisms shared by at least 5 samples across all the data, independent of the haplogroups or phenotypes. The algorithm looks for combinations of sets of mutations (bi-cliques) that are shared by five or more individuals in the data, using a recursive algorithm that combines the sets onto bigger sets until all maximal sets are identified. The software for this algorithm along with a brief description is available at http://genome.cs.iastate.edu/supertree/download/biclique. These bi-cliquesto other haplogroups and is also a non-synonymous mutation. The population structure can be identified by analyzing the large eigenvalues of the SNP-SNP correlation matrix. The SNPs with large coefficients in these eigenvectors represent the polymorphisms which will be found on the tree representing the phylogeny of the samples in the data. If the data is projected onto these large eigenmode principal components, it will split into classes representing the phylogeny of their common ancestry. Thus, the eigenvectors corresponding to the set of large eigenmodes represent variation due to population structure and those corresponding to the set of small eigenmodes represent potentially real functional polymorphisms. If there is a strong correlation between the phenotype and the SNPs with large coefficients in the eigenvectors of large eigenmodes, then this represents population structure related events such as diet, climate, founder effects, etc. Conversely, if the correlation is functional, there should be a strong correlation between the phenotype and the projection of the SNP matrix onto its lower eigenmodes. Such a correlation would be expected to be similar to pattern-based feature selection.

The score mentioned above is essentially the ratio between the numbers of times SNP i and SNP j appear together in the same enriched pattern and the total number of patterns that have both mutations. The agreement matrix is diagonal and symmetric. The diagonal entries represent the greatest possible correlation between SNP i and SNP j. Setting the diagonal entries to 1 sets a threshold in the matrix for the greatest possible correlation between SNP i and SNP j. This is useful when we use the matrix to identify correlated cliques by thinking of it as a connectivity matrix for a graph where nodes (labeled by index i) are SNP locations and nodes i and j are considered linked by a bond if their correlation is greater than some threshold t. By successively lowering the value of the threshold from higher to lower values, one can identify the core set of SNPs that form a clique, which is a set of SNPs where each pairwise correlation exceeds the threshold. Rows and columns of the matrix are then sorted (clustered) to place the clique SNPs in the top-left corner. Color coding of the resulting matrix based on the entry values produces a heat map showing mtSNPs at different levels of enrichment.

To look for an association between the mtDNA polymorphisms and their haplogroups with nuclear mutations and pathways, we analyzed the 44 Japanese samples in the HapMap database. Of these, 16 samples were classified by HapMap as belonging to the D clade using mtDNA markers. However, the SNP density in the HapMap database was insufficient for further sub-classification into D sub-haplogroups. Enrichment of mutations in the samples from the D clade with respect to the rest of the haplogroups was identified and its significance assessed using a chi-squared test.

The decision on where to place the cutoff to separate high eigenmodes from low eigenmodes is made using the Tracy-Widom distribution (see [21] for a detailed description and references to the literature), which provides the basis for the null hypothesis. Consider a matrix M of dimension N x N SNP samples (where N and N represent the number of SNPs and the SNP samples number of samples in the original data). Assume that the entries M are independent standard Normal Gaussian distributed variables for each SNP location. The product of M and its transpose MT represents the correlation matrix of SNP-SNP correlations which would be obtained by chance. The distribution of eigenvalues of MMT is the Tracy-Widom distribution which represents the null-probability to get a high eigenvalue by chance in data without population structure. We use a simple method (chosen to have a p-value, 0.05) to find the cutoff x in eigenvalue to separate population structure from functional polymorphisms. We identify the highest k eigenvalues in the real data that represent more than a fraction f=0.95 of the variation in the data as those representing population structure [21]. x is easily obtained by first finding k by solving: f= [S k l]/N where the SNP eigenvalues l are sorted from highest to lowest value. The value of x is then obtained from: x= (l+k)/2.