To measure the degree of association of an mtSNP to longevity, we define a mtSNP enrichment score L follows: S

Haplogroups associated with longevity were identified as those with a larger proportion of enriched patterns out of the total number of patterns associated with the haplogroup. The Fisher Exact test was used to examine the significance of the association between patterns and haplogroups. This test gives the exact probability of seeing a certain association between the two categorical variables by chance. We looked for associations between polymorphisms in the enriched patterns by identifying mutations which appear together in patterns and are simulta- neously strongly associated with the longevity phenotypes. This was done by creating an agreement matrix M = {m } of size n x n, ij where n is the number of mtSNPs seen in the patterns. The entries

This score is defined for each SNP separately. Consider the case where we are computing this score for centenarians. f T is the S fraction of samples in the centenarians that have the SNP, f C is S the fraction of samples in the control group (healthy non-obese males) that have the SNP. s NT is the standard deviations of the S fractions of samples in the collection of the 6 other non-

m are defined so that they measure the beneficial effect of SNP i ij and SNP j if found in the same individual. Let P be the space of all patterns in the data and P 5P the subspace representing enriched e patterns in semi-supercentenarians relative to healthy normals (q- value,0.05) and p [P a pattern in this space; then the entries in k the matrix M are:

from a common ancestor (ie. it is due to the phylogeny of haplogroups). Such correlations often introduce a high number of false positive spurious correlations in association studies.

Several methods [18–21] have been proposed to factor out associations due to population structure and identify real functional polymorphisms. For instance, structure association [19] classifies individuals into different clusters and looks for correlations within each cluster. Population genetic information is a combination of population structure and individual variations. The general idea in distinguishing mtDNA population structure polymorphisms from functional ones is to compare the eigenmodes of the actual SNP-SNP correlation matrix with those of a matrix of equal size but without population structure (generated using Normal Gaussian variables as described below), which, by construction, does not have any population structure[10,18–21]. Population structure in the real mtDNA data shows up as large eigenvalues of the SNP-SNP correlation matrix. One can identify the polymorphisms that represent this population structure by looking at the eigenvectors corresponding to these large eigenval- ues. 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 represents 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. Such correlations would then most probably originate in 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

This score is similar to the pattern based feature selection defined in [16]. It 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 (because SNP i and SNP j are always found together in the same pattern if i = 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 the nodes (labeled by the 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 pair- wise 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 [5]. 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.