BACKGROUND
allele frequencies vary across populations because of differences in ancestry; these differences arise from many factors such as migration, selection and drift.
hence, populations are genetically substructured.
the information obtained from resolving population substructure can be used to infer population history.
furthermore, human disease association studies must account and correct for the population substructure to reduce spurious associations and reveal the predisposing factors of disease  <cit> .
analysis of population stratification must meet four main challenges namely:  detecting structure,  assigning individuals to subpopulations,  determining the number of optimal, or primal, subpopulations  and  determining the proportions of ancestral subpopulations   <cit> .
with the advent of high throughput genotyping, increasingly large genotypic datasets  arrays from  <dig> individuals <cit> ) will provide progressively difficult challenges for population structure analysis.
therefore, to keep abreast with the ever increasing size and complexity of genotypic data, refinement of existing analytical methods and entirely novel approaches will be needed to resolve subpopulations.
several different methods have been proposed to address some aspects of the population substructure problem.
these methods can be categorized into two main approaches, namely parametric and non-parametric-based.
structure is the "gold standard" parametric-based algorithm for population stratification analysis  <cit>  because it addresses all four substructure analysis challenges.
however, structure imposes a high computational burden and it is thus impractical for the large datasets typically analyzed nowadays.
structure was originally designed to be used with microsatellite markers, which are generally more informative than snps.
nonetheless, it is generally accepted that the computational burden of analyzing large snp datasets with structure is a trade-off, since large numbers of snp markers can be easily typed in parallel on array platforms, in contrast to the laborious electrophoretic methods for typing microsatellites.
structure also has other weaknesses, mainly its inference of k, which requires extensive statistical testing of several structure runs performed with increasing k. structure's inference of k can also vary according to the model used  <cit> , hence the determination of admixture, which is highly dependent on the k value used needs to be interpreted with caution.
alternative parametric methods, such as l-pop  <cit> , psmix  <cit> , frappe  <cit> , baps  <cit> , and tess  <cit>  are more computationally efficient.
these algorithms are used mainly to infer ancestry  using statistical inference methods.
for non-parametric methods, the algorithms in this class do not require model assumptions.
principal components analysis  is the most widely used method for visualizing structure which uses a covariance matrix for eigenanalysis, allowing representation of individuals as data points in scatter-plots.
principal coordinate analysis  is an alternative method for eigenanalysis which uses an allele-sharing distance  matrix, and gives different scatter-plot patterns from pca  <cit> .
note that pca and pcoa are not methods for assigning individuals nor estimating k and are often used merely to visualize the population structure trend.
the most popular pca-based algorithm applied to population structure analysis is eigenstrat/smartpca  <cit> , which has been used by several investigators for large datasets typically required for studies of human population structure and disease association  <cit> .
this algorithm employs a computationally-efficient variant of eigenanalysis to report the probability of population substructure according to tracy-widom  distribution.
in a typical population dataset, genetic distances vary among subpopulations and pca scatter-plots can reveal the most genetically isolated subpopulations as distinct clusters of individuals in a small number of principal components.
hence, supervised clustered with prior assumption of the number of k subpopulation clusters can be done to assign individuals.
conversely, closely related subpopulations will occupy a confined feature space and appear as a conglomerate.
for example, in the scatter-plot of pc <dig> versus pc <dig>  conglomerates containing individuals with different population labels are frequently observed.
in some cases, the distinction between closely related subpopulations is apparent in a greater number of principal components  <cit> .
thus, in order to resolve closely related subpopulations, individuals must be separated using a clustering algorithm working in multidimensional pca space  <cit> .
clustering algorithms require separation in axes of variation.
however, clusters in some axes may merge into a single cluster, and hence clustering algorithms can become confused when too many axes of variation are used  <cit> .
in general, the informative axes of variation are contained within the rank of matrix  <cit> .
therefore, the number of principal components should be optimized and not exceed a certain number for each dataset.
one way to improve the resolution of closely-related subpopulations in pca scatter-plots is by removing genetically distant individuals from the dataset.
in the investigation of european human genetic substructure using 300k snp arrays  <cit> , it was found that prior exclusion of individuals belonging to certain groups improved substructure resolution of the other groups, e.g.
removal of ashkenazi jewish individuals led to clearer substructuring of other northern european groups.
this data "cleaning" approach is clearly advantageous, although the method as described in  <cit>  is ad hoc and unable to detect and remove subtle outliers  <cit> .
clearly, this approach is not feasible for datasets composed of individuals presumed to belong to a homogenous population without any distinguishing labels, for instance disease association studies carefully controlled for ethnicity and geographical origin.
with sufficient number of markers and individuals, cryptic structure in an apparently homogenous population can be detected using pca  <cit> , which cannot be resolved by current unsupervised clustering methods, with no assumptions of k  <cit> .
to determine the primal k for unsupervised clustering, the gap statistic  <cit>  is employed on the awclust results  <cit>  and density-based means clustering results  <cit> .
alternatively, the bayesian information criterion  approach for determining k can be applied to the clustering results  <cit> .
calculating the gap statistic and bic are computationally intensive, thus these approaches are impractical for highly structured datasets.
furthermore, these approaches are sensitive to noisy non-informative pcs, which may explain why they are not appropriate for highly structured datasets with a large k. all unsupervised clustering approaches currently applied to pca do not assign individuals into subpopulations according to genetic distance between subpopulations in a fully comprehensive and systematic fashion.
these algorithms thus have insufficient discriminatory power to assign individuals to subpopulations and determine k for highly structured datasets.
in this study, we propose a non-parametric analytical framework which incorporates several key refinements of the pca-based approach.
the new algorithm, which we call iterative pruning pca  addresses three of the main challenges for population structure analysis, namely detection of structure, assigning individuals to subpopulations and determining the primal k with greater accuracy than previously proposed algorithms.
the ippca algorithm utilizes a novel unsupervised clustering heuristic which markedly improves resolution of population substructure by an iterative process.
in this method, groups of individuals are systematically bisected according to genetic similarity at each step, continuing until a termination point  is reached revealing the underlying subpopulations.
RESULTS
algorithm
the ippca algorithm utilizes non-redundant principal components to construct a transformed domain of the input data, which can be mapped to pca space.
by means of selecting a limited number of principal components, dimension reduction can be achieved.
the pca domain allows each input individual to be represented as a datum point in a scatter-plot, or in clustering analysis.
the ippca technique constructs the transformed domain based on a covariance matrix of the data matrix containing snp genotypic data encoded as  <dig>   <dig> or  <dig> elements.
where m and n are the number of markers and individuals respectively.
note that m is normally much larger than n.
since the covariance matrix is usually a large square matrix, it is memory and computationally intensive to compute the pca space.
however, there is an alternative technique to compute the transformed domain with less computational burden  <cit> .
instead of using the data covariance matrix, the pca space can be constructed by decomposing to a modified data matrix xxt, which is much smaller than the covariance matrix.
for example, a dataset with  <dig> individuals and  <dig> markers would have  <dig> ×  <dig> elements in the covariance matrix compared to  <dig> ×  <dig> elements in the xxt matrix.
the modified data matrix can be factored as usvt = xxt where
then, the eigenvectors can be computed by
where k is the rank of the data matrix and  are the eigenvectors.
then, the pca space is constructed based on these eigenvectors.
because ippca is sensitive to the data pattern, data quality is crucial for accuracy of the algorithm.
typically, it is necessary to clean the data before performing ippca.
technical limitations in genotyping occasionally lead to missing values at some loci.
to check whether missing data by itself can create substructure, all missing data are encoded as zero and other loci are encoded as one.
the 0- <dig> encoded dataset is analyzed by smartpca  <cit> .
if substructure can be observed as clear outlier individuals on the periphery of the two pc scatter-plot, these individuals can be removed from the dataset, as suggested by  <cit> .
before performing ippca, a quality control check is performed on the 0-1- <dig> encoded data matrix.
in this case, frequency counts are computed on each locus to ensure that entries encoded as zero are homozygous major allele , entries encoded as one are heterozygous and entries encoded as two are homozygous minor allele.
the pre-processing steps and the ippca framework can be summarized as follows:
pre-processing steps
check if missing values in the input dataset cause detectable substructure using eigenstrat/smartpca and if significant substructure is reported, remove individuals with missing data which cause substructure .
ippca steps
<dig>  make matrix xi for each data group, i.e.
dataset or nested dataset which contains substructure.
<dig>  use singular value decomposition   <cit>  to factorize the  data into
<dig>  project all individuals into pc space using the number of pcs equal to the data matrix rank  <cit> .
<dig>  check terminating condition on the si using the tw test statistic implemented in eigenstrat/smartpca  <cit> .
the default tw p-value threshold used for detectable structure is conservative  and lies well above the baik ben arous péché  threshold for significance among empirically tested datasets .
terminate if tw test statistic is insignificant for the first pc
otherwise, proceed to the next step
<dig>  apply fuzzy c-means  <cit>  to separate individuals xi into two clusters.
<dig>  repeat from step  <dig> until all the data are terminated.
when all the iterative processes are terminated, the number of subpopulations can be determined by counting all the terminal nodes .
note that replicate ippca runs are typically performed to test the robustness of the clustering algorithm, which could affect the assignment accuracy and determination of k. for datasets with simple structures, replicate runs may be unnecessary; however, the extra computational effort of performing replicate runs is minimal.
testing
the power and robustness of the proposed ippca algorithm was explored and optimized using simulated datasets.
the performance of ippca was then tested on three real datasets, namely hapmap, bovine, and shriver's datasets.
finally, we compared the results of our algorithm with the results from existing tools: structure, baps and awclust.
structure version  <dig>  was downloaded from j. pritchard's website  <cit>  and applied using the following parameters:  <dig> burn-ins,  <dig> runs, admixture model, no ld model.
individuals were assigned to subpopulations according to the highest reported probability value.
for baps, the software was downloaded from  <cit>  and executed using the mixture model.
for awclust analysis, awclust was downloaded from  <cit>  and the algorithm's default parameters were selected.
iterative pruning pca clustering: a way to improve discriminatory power
the program genome  <cit>  was employed to generate simulated genotypic data under the wright-fisher neutral coalescent model   <cit> .
three evolutionary models  were constructed .
the model  <dig> dataset  contains three subpopulations derived from two ancestral populations.
the model  <dig> dataset  contains five independent subpopulations with no admixture.
the model  <dig> datasets  contain  <dig> subpopulations derived from three ancestral populations.
parameter settings used to generate each model are as follows:
the model  <dig> dataset parameters:
-pop  <dig>  <dig>  <dig>  <dig> -c  <dig> -s  <dig> -n model <dig> txt
the model  <dig> dataset parameters:
-pop  <dig>  <dig>  <dig>  <dig>  <dig>  <dig> -c  <dig> -s  <dig> -n model <dig> txt
the model  <dig> dataset parameters:
-pop  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig>  <dig> -c  <dig> -s  <dig> -n model <dig> txt
using the above parameters, we generated  <dig> snps for each simulated dataset.
note that the model  <dig> population history was used to generate  <dig> datasets to test the robustness of ippca.
all simulated datasets and the population history files  analyzed in this study can be downloaded from http://www4a.biotec.or.th/gi/tools/ippca
the performance and robustness of ippca to resolve structure were investigated using simulated datasets of increasing complexity.
two simple population structure models  and one complex model  were simulated using the genome tool  <cit> .
for the first two simple models , ippca can resolve k consistent with the models and assign all individuals correctly to the corresponding subpopulations .
for the highly complex model ,  <dig> simulated datasets were generated using the same evolutionary model.
the structure resolved by ippca was highly consistent with the model, for both number of inferred k and the individuals assigned to each subpopulation , see additional file 1).
to test the reproducibility of the clustering algorithm, ten replicates of ippca were performed on each data set.
the results for each dataset were reproduced exactly, with no deviation in individual assignment or inference of k between replicates in each case .
assignment of individuals to subpopulations in real datasets is reproducible and consistent with population labels
three real datasets, namely hapmap, bovine, and shriver's, were analyzed in this work.
the hapmap dataset, retrieved from  <cit> , comprises individuals with four population labels: han chinese from beijing , japanese from tokyo , caucasian european from utah , and yoruba from ibadan  with  <dig> snps.
fifty thousand snps were uniformly re-sampled from this snp pool  <cit> .
starting from the first marker, a moving window was used to select snps in an even spacing fashion, such that every 30th marker was selected from the  <dig> markers .
data pre-processing ippca was performed and two outlier jpt individuals were removed.
the bovine dataset was downloaded from  <cit> .
the bovine snp data  are publicly available as part of the bovine genome project  <cit> .
after data pre-processing, no outliers were detected.
shriver's worldwide human snp dataset of  <dig> individuals with  <dig> different ethnic/geographical labels was provided by prof. mark d. shriver, which is a dataset expanded from the one originally published in  <cit> .
this dataset consists of  <dig> snps for each individual, evenly distributed over the entire genome.
after data pre-processing, no outliers were detected.
the hapmap dataset was analyzed by ippca, which contains individuals from four distinct geographical regions .
all individuals in each of the four subpopulations defined by ippca share the same distinguishing population label .
the yri subpopulation was defined in iteration  <dig> while the ceu was defined in iteration  <dig>  finally, the chb and jpt subpopulations were defined in iteration  <dig>  exactly the same assignment results were obtained from ten replicates using  <dig> snps and a single ippca run using the entire  <dig> snp collection .
the bovine dataset contains individuals from nine breeds considered to be genetically distinct subpopulations.
the brahman  breed cattle are zebu , considered a sub-species very distinct from the taurine cattle breeds.
santa gertrudis  is a composite breed derived from brm and shorthorn breed cattle.
the other breeds, angus , charolais , limousin , hereford , norwegian red , jersey  and holstein  are taurine cattle and european in origin .
scatter-plot analysis of the entire bovine dataset showed that individuals from the hfd, jer, hol, lms, ang, chl and nrc taurine breeds appear as a conglomerate and are separated from brm and sgt individuals .
figure  <dig> shows the resulting consensus subpopulation tree from ten ippca replicates, which all gave the same results .
the ippca program required six iterations to define all subpopulations in the bovine dataset.
after the second iteration, the brm and sgt cluster was divided satisfying the termination criterion, thus defining two subpopulations composed of brm and sgt individuals, respectively.
additionally, a third subpopulation composed of jer individuals was defined and separated from the taurine cluster.
after more iterations of ippca, a further six subpopulations were defined in which each subpopulation is largely composed of individuals of the same breed.
shriver's dataset was then analyzed by ippca.
from the scatter-plot analysis of the entire dataset, it can be observed that individuals are broadly grouped according to their geographical origins with some overlap of individuals with different labels .
the consensus ippca result showed that after the second iteration of ippca, a subpopulation composed of african americans and a puerto rican individual was defined.
after further iterations of ippca, more subpopulations were defined with each containing individuals with shared geographical and/or ethnic origins.
after six iterations, twelve subpopulations were defined with no further substructure found .
subpopulation assignments were robust.
only one ippca replicate differed from the consensus .
the assignments of individuals to subpopulations and k inferred by ippca were compared with other algorithms.
table  <dig> shows comparison between different algorithms for inferring k from  <dig> datasets.
for ippca, the inference of k was highly robust, with variation observed only among the most highly structured model  <dig> populations.
there was no concordance between the algorithms for inference of k. given the discordancy between the algorithms, we then investigated the individual assignments made by each algorithm.
<dig> not applicable since awclust gap statistics limits k < 8
<dig> not done owing to the computational constraint
<dig> modal value from  <dig> simulated datasets
<dig> there are two subpopulations with no individuals assigned to them
for datasets of low complexity, assignment of individuals to subpopulations was broadly consistent among the structure, baps, awclust, and ippca algorithms .
given the greater discordance between algorithms for inference of k from highly structured datasets, a more detailed comparison of individual assignments to subpopulations was made between structure, baps and ippca.
the comparison was made using shriver's highly structured dataset for the k reported by each algorithm .
each of the twelve subpopulations defined by ippca contain similar number of individuals , and the assignments of individuals to subpopulations sp- <dig>  sp- <dig>  sp- <dig>  sp- <dig>  sp- <dig>  sp- <dig>  sp- <dig> and sp- <dig> are consistent with the population labels.
four subpopulations, namely sp- <dig>  sp- <dig>  sp- <dig> and sp- <dig> contain individuals of more than one population label.
the subpopulations assigned by structure and baps differed markedly to ippca in the number of individuals contained within each.
for structure, two subpopulations have no assigned individuals, five subpopulations have fewer than ten individuals and two subpopulations have more than  <dig> assigned individuals.
for baps, there are two large subpopulations with more than  <dig> individuals and three smaller subpopulations.
inspection of the population labels of the assigned individuals shows that structure and baps assigned a subpopulation containing individuals from three geographically disparate african locations together with african americans and puerto ricans in contrast to ippca, which assigns african pygmy, west african and east african individuals as separate subpopulations sp- <dig>  sp- <dig> and sp- <dig>  respectively.
structure and baps also grouped nahua and quechua/peru individuals as one subpopulation and asian and south altaian individuals as another subpopulation.
however, ippca assigned these individuals to four separate subpopulations consistent with population labels .
in order to demonstrate the power of the iterative pruning approach, a comparison was made between the individual subpopulation assignments by ippca and clustering from pca result of the whole dataset .
the pca results from shriver's entire dataset were clustered using the same fuzzy c-means clustering algorithm to assign individuals into  <dig> clusters .
the number of clusters to be used for clustering was not calculated independently, e.g., using the gap statistic since this was not feasible for such a complex dataset.
it can be observed that clustering on non-iterative pca  results leads to notable differences in individual assignment.
for instance, there are three groups with fewer than ten individuals  and one conglomerate group containing  <dig> individuals .
furthermore, asian and south altaian individuals were assigned together, whereas east african and new guinea individuals were each separated into two subpopulations.
implementation
the ippca program was implemented in matlab version 2007a.
it is available in both graphical user interface  and matlab function.
gui ippca is suitable for small datasets, e.g.,  <dig> markers, while matlab function ippca can be used for larger datasets.
we are currently developing a compiled executable version of this program to broaden the user base.
the ippca software requires the input data in the following format as a csv  text file:
individual identifier, genotype data  for locus <dig>  genotype data locus <dig> ..., genotype data locus m
the tool for genotype data conversion , the ippca matlab source codes and instruction for use are available from http://www4a.biotec.or.th/gi/tools/ippca.
the outputs from ippca in text file format containing individual identifiers, scatter-plot coordinates, and eigenvalues for each iteration are provided.
discussion
practicality of ippca and comparison with other algorithms
we have demonstrated a novel pca-based analytical framework that accurately resolves population stratification including that of highly structured datasets.
with this tool, individuals are assigned to subpopulations and k is determined with high accuracy.
moreover, minimal computational effort is required.
for example, on a high performance computer , shriver's dataset requires over three days to compute by structure, approximately ten minutes for baps while ippca needed less than two minutes.
hence, the computational time and the complexity of the datasets were not limitations for ippca, unlike other algorithms, e.g., awclust limits the number of inferred k to seven or less.
improved clustering through pc selection
the trend observed among datasets analyzed in this study is that early iterations require more pcs for clustering than later ones .
this is in agreement with the findings of the authors of eigenstrat/smartpca, who showed that the number of significant eigenvectors  to resolve structure reflects the number of subpopulations  <cit> .
however, the number of k subpopulations is not simply defined by the number of significant pcs, since the actual number of pcs needed to reveal subpopulations varies in each case.
in ippca, the clustering process uses the optimal number of pcs , which varies among nested datasets according to the number of individuals at each iteration.
after each iteration of ippca, the nested datasets have progressively simpler structures so that fewer principal components are used for clustering.
inference of k
the inference of the number of optimal, or primal, k subpopulations and the individual assignment accuracy are critically dependent on each other.
high assignment accuracy allows the correct value of k to be inferred.
the structure, baps and awclust algorithms have lower assignment accuracy than ippca, and thus their inferences of k were found to be incorrect, at least for the simulated data.
for real data, structure, baps and awclust reported k =  <dig> for the hapmap dataset and could not resolve chb and jpt as separate subpopulations.
the resolution of chb and jpt subpopulations by ippca was consistent with the finding of  <cit> , who identified the subset of informative markers for separating these individuals into two subpopulations.
in order to define subpopulations from the pca clustering results, ippca uses a novel approach which considers only the eigenvalue distribution.
by this approach, subpopulations are defined by a standard criterion thus removing subjectivity from the definitions.
rigorous subpopulation definitions are currently lacking, since there is no agreement as to precisely what genetic variation accounts for population structure  <cit> .
the difficulty in defining subpopulations is the main reason why determining k is considered very challenging  <cit> .
although ippca's inference of k appears accurate and robust, there may be situations in which the inferred k is incorrect.
the proposed ippca algorithm would fail to resolve inadequately sampled subpopulations, since the individuals sampled from these subpopulations would be dismissed as pca outliers, or be assigned to other subpopulations.
conversely, spurious substructure may be reported among subpopulations with very large sampling, although our choice of a very conservative p-value for tw statistic in structure detection should militate against this possibility.
data quality is also another issue which could affect inference of k; spurious subpopulations may arise from missing data  and improper sampling of closely related individuals.
all of these potential problems are not specific to ippca however, and affect any population genetic analysis.
assignment accuracy
in terms of individual assignments, there were some notable differences between ippca, structure, and baps for shriver's dataset.
for the optimal number of subpopulations reported by structure  and baps  , assignments were inconsistent with what have been reported by other methods  <cit> .
from a population evolutionary perspective, some of the assignments made by structure and baps were not meaningful.
for instance, there were two groups that structure assigned no individuals to, while five other groups contained fewer than ten individuals .
by limiting k to twelve as what ippca predicted, the assignments made by structure changed with removal of the empty groups and amalgamation of south altaian individuals into one subpopulation .
however, some inconsistencies with accepted patterns of human population structure remained.
for example, the subpopulation with pan-african individuals remained.
for baps, it appears that this algorithm is less sensitive than ippca and structure, since the assignments revealed individuals with mixed labels .
a detailed head-to-head comparison between ippca, baps, and structure was done to demonstrate how our novel non-parametric framework compares against the most recent  and well known  parametric approaches.
comparisons of ippca against other parametric methods  were not made as they would not be valid, principally because none of these other parametric approaches infer k .
nonetheless, parametric approaches are still important for certain issues of population genetics not addressed by ippca.
i.e., determining ancestry proportions.
the ippca clustering approach differs from the approaches used by others for clustering pca results, e.g.
lee et al.
<cit>  who performed clustering on the entire dataset using a large number of pcs.
for highly structured populations, this kind of approach is not able to accurately assign individuals to subpopulations, irrespective of the clustering algorithm used  since the closely related subpopulations are confined in a small region of feature space .
the greatest problem for the ni-pca approach is in knowing the number of clusters to be used in clustering.
indeed, the analysis of highly structured datasets in this paper shows that ni-pca approach fails to accurately assign individuals, even when using the correct k inferred by ippca .
we chose fuzzy c-means for clustering since the number of clusters in each ippca iteration is restricted to two, hence a simple algorithm is sufficient.
furthermore, the cluster centroids determined by fuzzy c-means are more consistent compared with the commonly used k-means algorithm  <cit> , which is most important for subpopulation assignment in our case.
the clustering algorithm was shown to be highly consistent, as variation in individual assignment owing to variable clustering results from fuzzy c-means was observed only for shriver's dataset.
definition of subpopulations according to genetic distance
the iterative pruning approach also defines subpopulations in a manner reflecting the genetic distance, and in some cases the evolutionary path of each subpopulation.
as can be seen from the analysis of simulated datasets  and real datasets in figures  <dig>   <dig>   <dig>   <dig>   <dig>  closely related subpopulations are defined after more distantly related ones.
this iterative pruning process thus offers a systematic way to define subpopulations according to their degrees of relatedness to one another.
by removing the most distant individuals to create nested datasets, one is able to resolve substructure, which would not be revealed otherwise.
for more complex datasets containing subpopulations with individuals of recent admixed origins, these subpopulations were shown by ippca as those which contain assigned individuals with different population labels.
for instance, two subpopulations were defined from the bovine dataset containing individuals with different breed labels.
the overlap of nrc and hol individuals in a subpopulation is not unexpected, since nrc is not a pure breed and has hol ancestry.
similarly, the assignment of some sgt individuals to a subpopulation with taurine cattle reflects the fact that sgt is a composite zebu/taurine breed.
for shriver's dataset, which has a more complex structure than the bovine dataset, twelve subpopulations were defined by ippca with individuals assigned consistent with the group labels and the neighbor-joining tree shown in  <cit> .
four subpopulations appeared to be admixed containing individuals with different labels.
among these four admixed subpopulations, puerto rican individuals were assigned to two subpopulations.
these assignments reflect the puerto rican population history, in which their genomes still contain the signatures of ancestral european and african migrants  <cit> .
we are currently developing an admixture extension to ippca, which is outside the scope of this paper.
in this paper, we wished to provide a solid platform for ippca to demonstrate its accuracy in resolving all k primal subpopulations, which is crucial for admixture testing.
CONCLUSIONS
we propose some key refinements to the pca-based algorithm for improved resolution of population genetic stratification.
with this new method, individuals can be accurately assigned to subpopulations systematically, thus defining the optimal, or primal, k without any assumptions of individuals' origins or degree of relatedness to one another.
the power of the technique was demonstrated using datasets with known structure, although we think there is potential to reveal structure in datasets with cryptic stratification.
authors' contributions
ai, st wrote algorithms.
ai, pjs, aa, pw, cn, kc, jp, st analyzed data.
ai, pjs, st wrote the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
figure s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  s <dig>  and s <dig>  simulated data model  <dig> ippca  <dig> runs

 allele frequencies vary across populations because of differences in ancestry; these differences arise from many factors such as migration, selection and drift. hence, populations are genetically substructured. the information obtained from resolving population substructure can be used to infer population history. furthermore, human disease association studies must account and correct for the population substructure to reduce spurious associations and reveal the predisposing factors of disease. analysis of population stratification must meet four main challenges namely: detecting structure, assigning individuals to subpopulations, determining the number of optimal, or primal, subpopulations and determining the proportions of ancestral subpopulations. with the advent of high throughput genotyping, increasingly large genotypic datasets arrays from individuals ) will provide progressively difficult challenges for population structure analysis. therefore, to keep abreast with the ever increasing size and complexity of genotypic data, refinement of existing analytical methods and entirely novel approaches will be needed to resolve subpopulations. several different methods have been proposed to address some aspects of the population substructure problem. these methods can be categorized into two main approaches, namely parametric and non-parametric-based. structure is the "gold standard" parametric-based algorithm for population stratification analysis because it addresses all four substructure analysis challenges. however, structure imposes a high computational burden and it is thus impractical for the large datasets typically analyzed nowadays. structure was originally designed to be used with microsatellite markers, which are generally more informative than snps. nonetheless, it is generally accepted that the computational burden of analyzing large snp datasets with structure is a trade-off, since large numbers of snp markers can be easily typed in parallel on array platforms, in contrast to the laborious electrophoretic methods for typing microsatellites. structure also has other weaknesses, mainly its inference of k, which requires extensive statistical testing of several structure runs performed with increasing k. structure's inference of k can also vary according to the model used, hence the determination of admixture, which is highly dependent on the k value used needs to be interpreted with caution. alternative parametric methods, such as l-pop, psmix, frappe, baps, and tess are more computationally efficient. these algorithms are used mainly to infer ancestry using statistical inference methods. for non-parametric methods, the algorithms in this class do not require model assumptions. principal components analysis is the most widely used method for visualizing structure which uses a covariance matrix for eigenanalysis, allowing representation of individuals as data points in scatter-plots. principal coordinate analysis is an alternative method for eigenanalysis which uses an allele-sharing distance matrix, and gives different scatter-plot patterns from pca. note that pca and pcoa are not methods for assigning individuals nor estimating k and are often used merely to visualize the population structure trend. the most popular pca-based algorithm applied to population structure analysis is eigenstrat/smartpca, which has been used by several investigators for large datasets typically required for studies of human population structure and disease association. this algorithm employs a computationally-efficient variant of eigenanalysis to report the probability of population substructure according to tracy-widom distribution. in a typical population dataset, genetic distances vary among subpopulations and pca scatter-plots can reveal the most genetically isolated subpopulations as distinct clusters of individuals in a small number of principal components. hence, supervised clustered with prior assumption of the number of k subpopulation clusters can be done to assign individuals. conversely, closely related subpopulations will occupy a confined feature space and appear as a conglomerate. for example, in the scatter-plot of pc versus pc conglomerates containing individuals with different population labels are frequently observed. in some cases, the distinction between closely related subpopulations is apparent in a greater number of principal components. thus, in order to resolve closely related subpopulations, individuals must be separated using a clustering algorithm working in multidimensional pca space. clustering algorithms require separation in axes of variation. however, clusters in some axes may merge into a single cluster, and hence clustering algorithms can become confused when too many axes of variation are used. in general, the informative axes of variation are contained within the rank of matrix. therefore, the number of principal components should be optimized and not exceed a certain number for each dataset. one way to improve the resolution of closely-related subpopulations in pca scatter-plots is by removing genetically distant individuals from the dataset. in the investigation of european human genetic substructure using 300k snp arrays, it was found that prior exclusion of individuals belonging to certain groups improved substructure resolution of the other groups, e.g. removal of ashkenazi jewish individuals led to clearer substructuring of other northern european groups. this data "cleaning" approach is clearly advantageous, although the method as described in is ad hoc and unable to detect and remove subtle outliers. clearly, this approach is not feasible for datasets composed of individuals presumed to belong to a homogenous population without any distinguishing labels, for instance disease association studies carefully controlled for ethnicity and geographical origin. with sufficient number of markers and individuals, cryptic structure in an apparently homogenous population can be detected using pca, which cannot be resolved by current unsupervised clustering methods, with no assumptions of k. to determine the primal k for unsupervised clustering, the gap statistic is employed on the awclust results and density-based means clustering results. alternatively, the bayesian information criterion approach for determining k can be applied to the clustering results. calculating the gap statistic and bic are computationally intensive, thus these approaches are impractical for highly structured datasets. furthermore, these approaches are sensitive to noisy non-informative pcs, which may explain why they are not appropriate for highly structured datasets with a large k. all unsupervised clustering approaches currently applied to pca do not assign individuals into subpopulations according to genetic distance between subpopulations in a fully comprehensive and systematic fashion. these algorithms thus have insufficient discriminatory power to assign individuals to subpopulations and determine k for highly structured datasets. in this study, we propose a non-parametric analytical framework which incorporates several key refinements of the pca-based approach. the new algorithm, which we call iterative pruning pca addresses three of the main challenges for population structure analysis, namely detection of structure, assigning individuals to subpopulations and determining the primal k with greater accuracy than previously proposed algorithms. the ippca algorithm utilizes a novel unsupervised clustering heuristic which markedly improves resolution of population substructure by an iterative process. in this method, groups of individuals are systematically bisected according to genetic similarity at each step, continuing until a termination point is reached revealing the underlying subpopulations.  algorithm the ippca algorithm utilizes non-redundant principal components to construct a transformed domain of the input data, which can be mapped to pca space. by means of selecting a limited number of principal components, dimension reduction can be achieved. the pca domain allows each input individual to be represented as a datum point in a scatter-plot, or in clustering analysis. the ippca technique constructs the transformed domain based on a covariance matrix of the data matrix containing snp genotypic data encoded as or elements. where m and n are the number of markers and individuals respectively. note that m is normally much larger than n. since the covariance matrix is usually a large square matrix, it is memory and computationally intensive to compute the pca space. however, there is an alternative technique to compute the transformed domain with less computational burden. instead of using the data covariance matrix, the pca space can be constructed by decomposing to a modified data matrix xxt, which is much smaller than the covariance matrix. for example, a dataset with individuals and markers would have × elements in the covariance matrix compared to × elements in the xxt matrix. the modified data matrix can be factored as usvt = xxt where then, the eigenvectors can be computed by where k is the rank of the data matrix and are the eigenvectors. then, the pca space is constructed based on these eigenvectors. because ippca is sensitive to the data pattern, data quality is crucial for accuracy of the algorithm. typically, it is necessary to clean the data before performing ippca. technical limitations in genotyping occasionally lead to missing values at some loci. to check whether missing data by itself can create substructure, all missing data are encoded as zero and other loci are encoded as one. the 0- encoded dataset is analyzed by smartpca. if substructure can be observed as clear outlier individuals on the periphery of the two pc scatter-plot, these individuals can be removed from the dataset, as suggested by. before performing ippca, a quality control check is performed on the 0-1- encoded data matrix. in this case, frequency counts are computed on each locus to ensure that entries encoded as zero are homozygous major allele, entries encoded as one are heterozygous and entries encoded as two are homozygous minor allele. the pre-processing steps and the ippca framework can be summarized as follows: pre-processing steps check if missing values in the input dataset cause detectable substructure using eigenstrat/smartpca and if significant substructure is reported, remove individuals with missing data which cause substructure. ippca steps make matrix xi for each data group, i.e. dataset or nested dataset which contains substructure. use singular value decomposition to factorize the data into project all individuals into pc space using the number of pcs equal to the data matrix rank. check terminating condition on the si using the tw test statistic implemented in eigenstrat/smartpca. the default tw p-value threshold used for detectable structure is conservative and lies well above the baik ben arous péché threshold for significance among empirically tested datasets. terminate if tw test statistic is insignificant for the first pc otherwise, proceed to the next step apply fuzzy c-means to separate individuals xi into two clusters. repeat from step until all the data are terminated. when all the iterative processes are terminated, the number of subpopulations can be determined by counting all the terminal nodes. note that replicate ippca runs are typically performed to test the robustness of the clustering algorithm, which could affect the assignment accuracy and determination of k. for datasets with simple structures, replicate runs may be unnecessary; however, the extra computational effort of performing replicate runs is minimal. testing the power and robustness of the proposed ippca algorithm was explored and optimized using simulated datasets. the performance of ippca was then tested on three real datasets, namely hapmap, bovine, and shriver's datasets. finally, we compared the results of our algorithm with the results from existing tools: structure, baps and awclust. structure version was downloaded from j. pritchard's website and applied using the following parameters: burn-ins, runs, admixture model, no ld model. individuals were assigned to subpopulations according to the highest reported probability value. for baps, the software was downloaded from and executed using the mixture model. for awclust analysis, awclust was downloaded from and the algorithm's default parameters were selected. iterative pruning pca clustering: a way to improve discriminatory power the program genome was employed to generate simulated genotypic data under the wright-fisher neutral coalescent model. three evolutionary models were constructed. the model dataset contains three subpopulations derived from two ancestral populations. the model dataset contains five independent subpopulations with no admixture. the model datasets contain subpopulations derived from three ancestral populations. parameter settings used to generate each model are as follows: the model dataset parameters: -pop -c -s -n model txt the model dataset parameters: -pop -c -s -n model txt the model dataset parameters: -pop -c -s -n model txt using the above parameters, we generated snps for each simulated dataset. note that the model population history was used to generate datasets to test the robustness of ippca. all simulated datasets and the population history files analyzed in this study can be downloaded from http://www4a.biotec.or.th/gi/tools/ippca the performance and robustness of ippca to resolve structure were investigated using simulated datasets of increasing complexity. two simple population structure models and one complex model were simulated using the genome tool. for the first two simple models, ippca can resolve k consistent with the models and assign all individuals correctly to the corresponding subpopulations. for the highly complex model, simulated datasets were generated using the same evolutionary model. the structure resolved by ippca was highly consistent with the model, for both number of inferred k and the individuals assigned to each subpopulation, see additional file 1). to test the reproducibility of the clustering algorithm, ten replicates of ippca were performed on each data set. the results for each dataset were reproduced exactly, with no deviation in individual assignment or inference of k between replicates in each case. assignment of individuals to subpopulations in real datasets is reproducible and consistent with population labels three real datasets, namely hapmap, bovine, and shriver's, were analyzed in this work. the hapmap dataset, retrieved from, comprises individuals with four population labels: han chinese from beijing, japanese from tokyo, caucasian european from utah, and yoruba from ibadan with snps. fifty thousand snps were uniformly re-sampled from this snp pool. starting from the first marker, a moving window was used to select snps in an even spacing fashion, such that every 30th marker was selected from the markers. data pre-processing ippca was performed and two outlier jpt individuals were removed. the bovine dataset was downloaded from. the bovine snp data are publicly available as part of the bovine genome project. after data pre-processing, no outliers were detected. shriver's worldwide human snp dataset of individuals with different ethnic/geographical labels was provided by prof. mark d. shriver, which is a dataset expanded from the one originally published in. this dataset consists of snps for each individual, evenly distributed over the entire genome. after data pre-processing, no outliers were detected. the hapmap dataset was analyzed by ippca, which contains individuals from four distinct geographical regions. all individuals in each of the four subpopulations defined by ippca share the same distinguishing population label. the yri subpopulation was defined in iteration while the ceu was defined in iteration finally, the chb and jpt subpopulations were defined in iteration exactly the same assignment results were obtained from ten replicates using snps and a single ippca run using the entire snp collection. the bovine dataset contains individuals from nine breeds considered to be genetically distinct subpopulations. the brahman breed cattle are zebu, considered a sub-species very distinct from the taurine cattle breeds. santa gertrudis is a composite breed derived from brm and shorthorn breed cattle. the other breeds, angus, charolais, limousin, hereford, norwegian red, jersey and holstein are taurine cattle and european in origin. scatter-plot analysis of the entire bovine dataset showed that individuals from the hfd, jer, hol, lms, ang, chl and nrc taurine breeds appear as a conglomerate and are separated from brm and sgt individuals. figure shows the resulting consensus subpopulation tree from ten ippca replicates, which all gave the same results. the ippca program required six iterations to define all subpopulations in the bovine dataset. after the second iteration, the brm and sgt cluster was divided satisfying the termination criterion, thus defining two subpopulations composed of brm and sgt individuals, respectively. additionally, a third subpopulation composed of jer individuals was defined and separated from the taurine cluster. after more iterations of ippca, a further six subpopulations were defined in which each subpopulation is largely composed of individuals of the same breed. shriver's dataset was then analyzed by ippca. from the scatter-plot analysis of the entire dataset, it can be observed that individuals are broadly grouped according to their geographical origins with some overlap of individuals with different labels. the consensus ippca result showed that after the second iteration of ippca, a subpopulation composed of african americans and a puerto rican individual was defined. after further iterations of ippca, more subpopulations were defined with each containing individuals with shared geographical and/or ethnic origins. after six iterations, twelve subpopulations were defined with no further substructure found. subpopulation assignments were robust. only one ippca replicate differed from the consensus. the assignments of individuals to subpopulations and k inferred by ippca were compared with other algorithms. table shows comparison between different algorithms for inferring k from datasets. for ippca, the inference of k was highly robust, with variation observed only among the most highly structured model populations. there was no concordance between the algorithms for inference of k. given the discordancy between the algorithms, we then investigated the individual assignments made by each algorithm. not applicable since awclust gap statistics limits k < 8 not done owing to the computational constraint modal value from simulated datasets there are two subpopulations with no individuals assigned to them for datasets of low complexity, assignment of individuals to subpopulations was broadly consistent among the structure, baps, awclust, and ippca algorithms. given the greater discordance between algorithms for inference of k from highly structured datasets, a more detailed comparison of individual assignments to subpopulations was made between structure, baps and ippca. the comparison was made using shriver's highly structured dataset for the k reported by each algorithm. each of the twelve subpopulations defined by ippca contain similar number of individuals, and the assignments of individuals to subpopulations sp- sp- sp- sp- sp- sp- sp- and sp- are consistent with the population labels. four subpopulations, namely sp- sp- sp- and sp- contain individuals of more than one population label. the subpopulations assigned by structure and baps differed markedly to ippca in the number of individuals contained within each. for structure, two subpopulations have no assigned individuals, five subpopulations have fewer than ten individuals and two subpopulations have more than assigned individuals. for baps, there are two large subpopulations with more than individuals and three smaller subpopulations. inspection of the population labels of the assigned individuals shows that structure and baps assigned a subpopulation containing individuals from three geographically disparate african locations together with african americans and puerto ricans in contrast to ippca, which assigns african pygmy, west african and east african individuals as separate subpopulations sp- sp- and sp- respectively. structure and baps also grouped nahua and quechua/peru individuals as one subpopulation and asian and south altaian individuals as another subpopulation. however, ippca assigned these individuals to four separate subpopulations consistent with population labels. in order to demonstrate the power of the iterative pruning approach, a comparison was made between the individual subpopulation assignments by ippca and clustering from pca result of the whole dataset. the pca results from shriver's entire dataset were clustered using the same fuzzy c-means clustering algorithm to assign individuals into clusters. the number of clusters to be used for clustering was not calculated independently, e.g., using the gap statistic since this was not feasible for such a complex dataset. it can be observed that clustering on non-iterative pca results leads to notable differences in individual assignment. for instance, there are three groups with fewer than ten individuals and one conglomerate group containing individuals. furthermore, asian and south altaian individuals were assigned together, whereas east african and new guinea individuals were each separated into two subpopulations. implementation the ippca program was implemented in matlab version 2007a. it is available in both graphical user interface and matlab function. gui ippca is suitable for small datasets, e.g., markers, while matlab function ippca can be used for larger datasets. we are currently developing a compiled executable version of this program to broaden the user base. the ippca software requires the input data in the following format as a csv text file: individual identifier, genotype data for locus genotype data locus..., genotype data locus m the tool for genotype data conversion, the ippca matlab source codes and instruction for use are available from http://www4a.biotec.or.th/gi/tools/ippca. the outputs from ippca in text file format containing individual identifiers, scatter-plot coordinates, and eigenvalues for each iteration are provided. discussion practicality of ippca and comparison with other algorithms we have demonstrated a novel pca-based analytical framework that accurately resolves population stratification including that of highly structured datasets. with this tool, individuals are assigned to subpopulations and k is determined with high accuracy. moreover, minimal computational effort is required. for example, on a high performance computer, shriver's dataset requires over three days to compute by structure, approximately ten minutes for baps while ippca needed less than two minutes. hence, the computational time and the complexity of the datasets were not limitations for ippca, unlike other algorithms, e.g., awclust limits the number of inferred k to seven or less. improved clustering through pc selection the trend observed among datasets analyzed in this study is that early iterations require more pcs for clustering than later ones. this is in agreement with the findings of the authors of eigenstrat/smartpca, who showed that the number of significant eigenvectors to resolve structure reflects the number of subpopulations. however, the number of k subpopulations is not simply defined by the number of significant pcs, since the actual number of pcs needed to reveal subpopulations varies in each case. in ippca, the clustering process uses the optimal number of pcs, which varies among nested datasets according to the number of individuals at each iteration. after each iteration of ippca, the nested datasets have progressively simpler structures so that fewer principal components are used for clustering. inference of k the inference of the number of optimal, or primal, k subpopulations and the individual assignment accuracy are critically dependent on each other. high assignment accuracy allows the correct value of k to be inferred. the structure, baps and awclust algorithms have lower assignment accuracy than ippca, and thus their inferences of k were found to be incorrect, at least for the simulated data. for real data, structure, baps and awclust reported k = for the hapmap dataset and could not resolve chb and jpt as separate subpopulations. the resolution of chb and jpt subpopulations by ippca was consistent with the finding of, who identified the subset of informative markers for separating these individuals into two subpopulations. in order to define subpopulations from the pca clustering results, ippca uses a novel approach which considers only the eigenvalue distribution. by this approach, subpopulations are defined by a standard criterion thus removing subjectivity from the definitions. rigorous subpopulation definitions are currently lacking, since there is no agreement as to precisely what genetic variation accounts for population structure. the difficulty in defining subpopulations is the main reason why determining k is considered very challenging. although ippca's inference of k appears accurate and robust, there may be situations in which the inferred k is incorrect. the proposed ippca algorithm would fail to resolve inadequately sampled subpopulations, since the individuals sampled from these subpopulations would be dismissed as pca outliers, or be assigned to other subpopulations. conversely, spurious substructure may be reported among subpopulations with very large sampling, although our choice of a very conservative p-value for tw statistic in structure detection should militate against this possibility. data quality is also another issue which could affect inference of k; spurious subpopulations may arise from missing data and improper sampling of closely related individuals. all of these potential problems are not specific to ippca however, and affect any population genetic analysis. assignment accuracy in terms of individual assignments, there were some notable differences between ippca, structure, and baps for shriver's dataset. for the optimal number of subpopulations reported by structure and baps, assignments were inconsistent with what have been reported by other methods. from a population evolutionary perspective, some of the assignments made by structure and baps were not meaningful. for instance, there were two groups that structure assigned no individuals to, while five other groups contained fewer than ten individuals. by limiting k to twelve as what ippca predicted, the assignments made by structure changed with removal of the empty groups and amalgamation of south altaian individuals into one subpopulation. however, some inconsistencies with accepted patterns of human population structure remained. for example, the subpopulation with pan-african individuals remained. for baps, it appears that this algorithm is less sensitive than ippca and structure, since the assignments revealed individuals with mixed labels. a detailed head-to-head comparison between ippca, baps, and structure was done to demonstrate how our novel non-parametric framework compares against the most recent and well known parametric approaches. comparisons of ippca against other parametric methods were not made as they would not be valid, principally because none of these other parametric approaches infer k. nonetheless, parametric approaches are still important for certain issues of population genetics not addressed by ippca. i.e., determining ancestry proportions. the ippca clustering approach differs from the approaches used by others for clustering pca results, e.g. lee et al. who performed clustering on the entire dataset using a large number of pcs. for highly structured populations, this kind of approach is not able to accurately assign individuals to subpopulations, irrespective of the clustering algorithm used since the closely related subpopulations are confined in a small region of feature space. the greatest problem for the ni-pca approach is in knowing the number of clusters to be used in clustering. indeed, the analysis of highly structured datasets in this paper shows that ni-pca approach fails to accurately assign individuals, even when using the correct k inferred by ippca. we chose fuzzy c-means for clustering since the number of clusters in each ippca iteration is restricted to two, hence a simple algorithm is sufficient. furthermore, the cluster centroids determined by fuzzy c-means are more consistent compared with the commonly used k-means algorithm, which is most important for subpopulation assignment in our case. the clustering algorithm was shown to be highly consistent, as variation in individual assignment owing to variable clustering results from fuzzy c-means was observed only for shriver's dataset. definition of subpopulations according to genetic distance the iterative pruning approach also defines subpopulations in a manner reflecting the genetic distance, and in some cases the evolutionary path of each subpopulation. as can be seen from the analysis of simulated datasets and real datasets in figures closely related subpopulations are defined after more distantly related ones. this iterative pruning process thus offers a systematic way to define subpopulations according to their degrees of relatedness to one another. by removing the most distant individuals to create nested datasets, one is able to resolve substructure, which would not be revealed otherwise. for more complex datasets containing subpopulations with individuals of recent admixed origins, these subpopulations were shown by ippca as those which contain assigned individuals with different population labels. for instance, two subpopulations were defined from the bovine dataset containing individuals with different breed labels. the overlap of nrc and hol individuals in a subpopulation is not unexpected, since nrc is not a pure breed and has hol ancestry. similarly, the assignment of some sgt individuals to a subpopulation with taurine cattle reflects the fact that sgt is a composite zebu/taurine breed. for shriver's dataset, which has a more complex structure than the bovine dataset, twelve subpopulations were defined by ippca with individuals assigned consistent with the group labels and the neighbor-joining tree shown in. four subpopulations appeared to be admixed containing individuals with different labels. among these four admixed subpopulations, puerto rican individuals were assigned to two subpopulations. these assignments reflect the puerto rican population history, in which their genomes still contain the signatures of ancestral european and african migrants. we are currently developing an admixture extension to ippca, which is outside the scope of this paper. in this paper, we wished to provide a solid platform for ippca to demonstrate its accuracy in resolving all k primal subpopulations, which is crucial for admixture testing.  we propose some key refinements to the pca-based algorithm for improved resolution of population genetic stratification. with this new method, individuals can be accurately assigned to subpopulations systematically, thus defining the optimal, or primal, k without any assumptions of individuals' origins or degree of relatedness to one another. the power of the technique was demonstrated using datasets with known structure, although we think there is potential to reveal structure in datasets with cryptic stratification. authors' contributions ai, st wrote algorithms. ai, pjs, aa, pw, cn, kc, jp, st analyzed data. ai, pjs, st wrote the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 figure s s s s s s s s s s s s s s s s s s s s s s s s s s s s s and s simulated data model ippca runs 
the computationally efficient non-parametric, chiefly principal components analysis -based methods are thus becoming increasingly relied upon for population structure analysis. for datasets with simple structures, the subpopulation assignments of individuals made by ippca were largely consistent with the structure, baps and awclust algorithms. this systematic subpopulation assignment approach removes the need for prior population labels, which could be advantageous when cryptic stratification is encountered in datasets containing individuals otherwise assumed to belong to a homogenous population. when subpopulations are closely related to one another, they overlap in pca space and appear as a conglomerate. a novel population structure analysis algorithm called iterative pruning pca was developed which assigns individuals to subpopulations and infers the total number of subpopulations present. as genotypic datasets become ever larger, it is increasingly difficult to correctly estimate the number of subpopulations and assign individuals to them. genotypic data from simulated and real population datasets with different degrees of structure were analyzed. therefore, populations are structured into genetically distinct subpopulations.
 non-random patterns of genetic variation exist among individuals in a population owing to a variety of evolutionary factors. therefore, populations are structured into genetically distinct subpopulations. as genotypic datasets become ever larger, it is increasingly difficult to correctly estimate the number of subpopulations and assign individuals to them. the computationally efficient non-parametric, chiefly principal components analysis -based methods are thus becoming increasingly relied upon for population structure analysis. current pca-based methods can accurately detect structure; however, the accuracy in resolving subpopulations and assigning individuals to them is wanting. when subpopulations are closely related to one another, they overlap in pca space and appear as a conglomerate. this problem is exacerbated when some subpopulations in the dataset are genetically far removed from others. we propose a novel pca-based framework which addresses this shortcoming.  a novel population structure analysis algorithm called iterative pruning pca was developed which assigns individuals to subpopulations and infers the total number of subpopulations present. genotypic data from simulated and real population datasets with different degrees of structure were analyzed. for datasets with simple structures, the subpopulation assignments of individuals made by ippca were largely consistent with the structure, baps and awclust algorithms. on the other hand, highly structured populations containing many closely related subpopulations could be accurately resolved only by ippca, and not by other methods.  the algorithm is computationally efficient and not constrained by the dataset complexity. this systematic subpopulation assignment approach removes the need for prior population labels, which could be advantageous when cryptic stratification is encountered in datasets containing individuals otherwise assumed to belong to a homogenous population. 