BACKGROUND
information about population structure, namely population stratification and admixture, is useful in a variety of situations, such as association studies of genes underlying complex traits, subspecies classification, genetic barrier detection, and evolutionary study  <cit> .
for example, it is very important to identify genetic ancestry and admixture in admixture mapping  <cit> .
the presence of population stratification or admixture may pose a practical nuisance as well.
in association studies, case-control design is often used to identify genetic variants underlying complex traits by comparing allele frequencies between unrelated individuals that are affected and those unaffected.
however, the presence of population stratification or admixture in the sample can lead to spurious associations between a candidate marker and a phenotype  <cit> .
in forensic studies, the identification of reference groups is central but becomes difficult when there exists population stratification  <cit> .
in the estimation of the magnitude of inbreeding, it is useful to distinguish between the causes for the excess homozygosity which might be consanguineous mating or population substructure, or an artifact due to factors like null alleles  <cit> .
in all these situations, identifying population stratification or admixture has been an important component.
population structure can be identified based on visible characters such as language, culture, physical appearance, and geographic region.
but this can be subjective and may bear no relevance to genetics.
evanno et al.
<cit>  gave a good example by mentioning migratory bats which can be found thousands of kilometers apart but from the same breeding roost in winter  <cit> .
statistical methods have been proposed to infer population stratification and individual admixture using multilocus genotype data  <cit> .
different methods use different statistical tools and population genetic assumptions.
pritchard et al.
<cit>  introduced a model-based clustering method to infer population structure and assign individuals to populations using multilocus genotype data.
they used bayesian formulation and generated the posterior distributions using a markov chain monte carlo  method based on gibbs sampling.
their main modeling assumptions are hardy-weinberg equilibrium  within populations and linkage equilibrium  between markers within each population.
falush et al.
<cit>  extended the method to allow for loose linkage between loci.
the method of corander et al.
<cit>  uses multilocus molecular markers and geographical information provided by the sampling design.
unlike the methods of pritchard et al.
<cit>  and falush et al.
<cit> , the methods of both dawson and belkhir  <cit>  and corander et al.
<cit>  can directly estimate the number of populations and assign individuals to the populations.
the main difference between the two approaches is the parametric assumption of the number of populations  <cit> .
corander et al.
<cit>  considered the geographical sampling design of the individuals and set the maximum number of populations allowed to be the number of locations sampled, whereas for dawson and belkhir  <cit> , it is the total number of individuals.
corander et al.
<cit>  generalized the approach of corander et al.
<cit>  and it became more similar to the approach of dawson and belkhir  <cit>  in terms of model assumptions and some technical details, especially when the data is specified for individual level analysis.
guillot et al.
<cit>  used spatial statistical models employing both landscape ecology and population genetics information, which is especially useful in situations of young populations exhibiting low genetic differentiation  <cit> .
excoffier et al.
<cit>  applied approximate bayesian computation method to the estimation of all the parameters of an explicit admixture model.
their method can easily deal with complex mutation models and partially linked loci and is superior when the admixture is more ancient  <cit> .
the majority of the methods for population structure inference are bayesian approaches  <cit>  with few exceptions such as tang et al.
<cit> , satten et al.
<cit> , wang  <cit> , and purcell and sham  <cit> .
meanwhile, several methods have been proposed for the assignment of individuals to populations  <cit> .
as for computer programs available based on existing methods, the majority are also based on bayesian mcmc methods, such as structure  <cit> , geneland  <cit> , baps/baps  <dig>  <cit> , and admixmap  <cit> , with the exception of l-pop <cit>  which is based on latent class analysis.
table  <dig> summarizes some of the commonly used software for population structure inference.
structure is the most commonly used program for population structure inference which has been used both on humans  <cit>  and other species  <cit>  .
we choose to compare the performance of our package with structure and l-pop .
implementation
we have developed an efficient r package, named psmix , for population stratification and individual admixture inference.
since r can be slow when computation is intensive, we implemented the expectation-maximization  algorithm  <cit>  using c programming language.
psmix is mainly based on the methods proposed in tang et al.
<cit>  and liu et al.
<cit> .
three models  are discussed in full detail in  <cit> .
the second one is equivalent to the model proposed in tang et al.
<cit> .
the first model is a special case of the second one.
in tang et al.
the method itself has been fully assessed by simulation studies  <cit> .
RESULTS
we used two real datasets from rosenberg et al.
<cit>  and one simulated dataset from tang et al.
<cit>  to demonstrate the functionality of psmix.
one real dataset contains two american populations, pima and surui with  <dig> and  <dig> individuals, respectively; the other contains two european populations, sardinian and russian with  <dig> and  <dig> individuals, respectively.
the simulated data set contains  <dig> individuals from each of the two ancestral populations, and  <dig> individuals from the admixed population.
the true individual admixture values of the admixed individuals are also available.
to evaluate the efficiency of psmix, we randomly selected  <dig> markers from the pima-surui dataset with no missing values and tried the four models available in structure <dig> .
burnin length and number of mcmc replications after burnin were both set to be  <dig>  in the analyses.
the time needed for each run of structure <dig>  increased almost linearly with the increase of number of clusters.
on our pc with pentium iii  <dig> mhz cpu and  <dig> mb sdram, when k =  <dig>  about two and a half minutes were needed for each run of structure <dig> .
for all psmix runs, we set the stopping criterion to be that the parameter difference <10- <dig> between consecutive iterations, or  <dig>  steps, whichever was reached first.
for the same pima-surui data with  <dig> markers, each run of psmix needed about  <dig> seconds.
to evaluate the accuracy of psmix, we compared the results of psmix with those of structure.
figure  <dig> gives a sample run for the pima-surui dataset using only the first  <dig> markers.
for the pima-surui dataset using the first  <dig> markers from the original data, the correlation coefficient between the results of psmix and structure was greater than  <dig> .
for the sardinian-russian dataset, when all  <dig> markers were used, both structure  <dig>   and psmix had one individual misclustered.
the correlation coefficient between the results was  <dig> .
the two methods produced very similar results.
this is consistent with the findings in tang et al.
<cit> .
figure  <dig> shows the results of structure, l-pop, and psmix.
we can see that the results of psmix are much closer to those of structure.
to evaluate the performance of psmix, we also used a simulated data set exhibiting population admixture.
from figure  <dig> we can see the psmix performs pretty well and the results are almost identical to those from structure.
discussion
we have implemented a likelihood based method of population structure inference into an efficient r package, psmix.
psmix can be used in population genetics and disease gene mapping, wherever population stratification or individual admixture is needed to be estimated from genetic markers.
compared with other available similar programs, psmix has several advantages.
first, it is computationally efficient and provides similar accuracy under realistic situations .
and thus the confidence intervals of the estimates can be constructed via resampling methods, e.g., the bootstrap method  <cit> .
second, as shown in tang et al.
<cit> , it performs a little better  under some conditions involving a small number of ancestors and markers.
we note that l-pop is also computationally efficient.
however, it is not clear if l-pop can perform better under such conditions.
third, it is very flexible.
it is likelihood based and can be easily incorporated into study designs, such as marker choice  <cit> .
the program is implemented as a public r package and can be easily extended and incorporated into other packages.
this is an advantage of psmix over structure and l-pop, which has only executable programs.
we would like to note that the examples used in this work are mainly for the purpose of demonstrating the r package, not for the purpose of the assessing the underlying method.
please refer to tang et al.
<cit>  for a detailed assessment of the methodology.
in our simulation and application to real data, psmix and structure gave very similar results.
this is not surprising because estimating parameters via maximum likelihood and maximum a posterior with flat prior is formally strictly similar, where psmix belongs to the former and structure belongs to the latter.
many studies have been performed to assess the ability of structure in assigning individuals to their populations of origin using either real data or simulated data  <cit> .
however, very limited studies have been performed to assess the ability of structure in detecting the number of populations.
recently, evanno et al.
<cit>  performed a systematic study on this issue using simulations.
they simulated amplified fragment length polymorphism  and microsatellite genetic data under three population structure models: the island model, a contact zone, and a hierarchical island model  <cit> .
their major finding is that the "log probability of data", an ad hoc criterion suggested by pritchard et al.
<cit>  for detecting the number of populations, does not provide a correct estimation of the number of populations most of the time  <cit> .
however, they found that another ad hoc statistic, which is based on the rate of change in the log probability of the data between successive numbers of populations, can accurately detect the uppermost hierarchical level of structure  <cit> .
they also found some other factors that can affect the detection of the number of populations  <cit> .
these findings are important and useful in that with the increasing usage of structure, they provide guidance on how to use structure to detect the number of populations.
however, psmix does not directly detect the number of populations in this version.
due to its computation efficiency, model selection methods such as akaike information criterion   <cit> , bayesian information criterion   <cit> , and even more general, penalized likelihood based methods  <cit>  can be used for this purpose.
the findings of evanno et al.
<cit>  may be incorporated into psmix as well.
this is one of our future works.
em approach and bayesian mcmc approach have their own advantages and disadvantages.
they both can trap in local modes, although theoretically speaking, bayesian mcmc approach can converge to the true value eventually, maybe after an unrealistic long time.
however, the bayesian mcmc approach, in addition, has the label switching problem.
two authors  of the paper where the method of structure was proposed  <cit>  mentioned in other papers  <cit>  on methods to deal with this problem.
although this issue is believed to be well addressed by structure, it does make the bayesian mcmc approach more complicated.
however, this topic is beyond the scope of this work.
from the users' point of view, they only see the computation efficiency and stability of the methods.
we think that it may be necessary to explicitly explain some details about the models mentioned in this work.
first, the orientation of tang et al.
<cit>  is different from that of structure, l-pop, and liu et al.
<cit> .
the goal of the former was to estimate individual admixture for the admixed individuals.
the original focus of the latter was to "identify discrete clusters roughly corresponding to subpopulations"  <cit> .
structure, l-pop, and liu et al.
<cit>  use methods for clustering, although they "can also be applied to an admixture model"  <cit> .
so initially, tang et al.
<cit>  faced a population  that is currently in hardy-weinberg equilibrium, but was created as the result of admixture at some point in the past.
however, as emphasized in tang et al.
<cit> , the problem may not be identifiable without the inclusion of pseudo-ancestors who are proxies of the true pure ancestry  <cit> .
here the nonidentifiablity issue is related to the problem, and by no means pertains to the method.
in other words, the nonidentifiablity issue exists and has nothing to do with the statistical methods to be used, if pseudo-ancestors are not included.
therefore, the actual data tang et al.
<cit>  dealt with consist of "i <dig> individuals from the admixed group, as well as ik subjects from each of the k ancestral populations"  <cit> , that is, a stratified "pooled" population.
so the actual data all these methods deal with are the same in the sense that the data consist of stratified populations within which hardy-weinberg equilibrium holds.
one major difference is that tang et al.
<cit>  only focus on the individual admixture of the people in the admixed population .
facing the same data, the method in tang et al.
<cit>  is for clustering as well, in spirit.
they included pseudo-ancestors and used clustering method in order to estimate individual admixture.
in other words, all the aforementioned methods are for population stratification, and can be applied to estimate individual admixture.
thus the comparisons made in this work are appropriate.
we also want to emphasize here the importance of inclusion of ancestral populations or their surrogates when individual admixture is needed; otherwise the problem may not be identifiable no matter what method to use.
CONCLUSIONS
in summary, we have implemented a new, likelihood based method for inference of population stratification and individual admixture which is available as a public r package.
although the package has several advantages over its peers, we strongly suggest that the users use different software in their analysis.
if the results from these software are consistent; this may provide more support for the results; if the results are not consistent, further investigation is needed.
a potential limitation is the assumption of independence among markers behind psmix, which will be addressed in future versions of psmix.
availability and requirements
project name: psmix
project home page:
operating system: ms windows, linux, mac
programming language: c, r
other requirements: r  <dig>  or higher
license: gpl
any restrictions to use by non-academics: none
authors' contributions
bw participated in the design of the study, implemented psmix, and helped to draft the manuscript; nl participated in the design of the study, performed the analysis, and drafted the manuscript; hz conceived the study, participated in its design and helped to draft the manuscript.
all authors read and approved the final manuscript.

 information about population structure, namely population stratification and admixture, is useful in a variety of situations, such as association studies of genes underlying complex traits, subspecies classification, genetic barrier detection, and evolutionary study. for example, it is very important to identify genetic ancestry and admixture in admixture mapping. the presence of population stratification or admixture may pose a practical nuisance as well. in association studies, case-control design is often used to identify genetic variants underlying complex traits by comparing allele frequencies between unrelated individuals that are affected and those unaffected. however, the presence of population stratification or admixture in the sample can lead to spurious associations between a candidate marker and a phenotype. in forensic studies, the identification of reference groups is central but becomes difficult when there exists population stratification. in the estimation of the magnitude of inbreeding, it is useful to distinguish between the causes for the excess homozygosity which might be consanguineous mating or population substructure, or an artifact due to factors like null alleles. in all these situations, identifying population stratification or admixture has been an important component. population structure can be identified based on visible characters such as language, culture, physical appearance, and geographic region. but this can be subjective and may bear no relevance to genetics. evanno et al. gave a good example by mentioning migratory bats which can be found thousands of kilometers apart but from the same breeding roost in winter. statistical methods have been proposed to infer population stratification and individual admixture using multilocus genotype data. different methods use different statistical tools and population genetic assumptions. pritchard et al. introduced a model-based clustering method to infer population structure and assign individuals to populations using multilocus genotype data. they used bayesian formulation and generated the posterior distributions using a markov chain monte carlo method based on gibbs sampling. their main modeling assumptions are hardy-weinberg equilibrium within populations and linkage equilibrium between markers within each population. falush et al. extended the method to allow for loose linkage between loci. the method of corander et al. uses multilocus molecular markers and geographical information provided by the sampling design. unlike the methods of pritchard et al. and falush et al., the methods of both dawson and belkhir and corander et al. can directly estimate the number of populations and assign individuals to the populations. the main difference between the two approaches is the parametric assumption of the number of populations. corander et al. considered the geographical sampling design of the individuals and set the maximum number of populations allowed to be the number of locations sampled, whereas for dawson and belkhir, it is the total number of individuals. corander et al. generalized the approach of corander et al. and it became more similar to the approach of dawson and belkhir in terms of model assumptions and some technical details, especially when the data is specified for individual level analysis. guillot et al. used spatial statistical models employing both landscape ecology and population genetics information, which is especially useful in situations of young populations exhibiting low genetic differentiation. excoffier et al. applied approximate bayesian computation method to the estimation of all the parameters of an explicit admixture model. their method can easily deal with complex mutation models and partially linked loci and is superior when the admixture is more ancient. the majority of the methods for population structure inference are bayesian approaches with few exceptions such as tang et al., satten et al., wang, and purcell and sham. meanwhile, several methods have been proposed for the assignment of individuals to populations. as for computer programs available based on existing methods, the majority are also based on bayesian mcmc methods, such as structure, geneland, baps/baps, and admixmap, with the exception of l-pop which is based on latent class analysis. table summarizes some of the commonly used software for population structure inference. structure is the most commonly used program for population structure inference which has been used both on humans and other species. we choose to compare the performance of our package with structure and l-pop. implementation we have developed an efficient r package, named psmix, for population stratification and individual admixture inference. since r can be slow when computation is intensive, we implemented the expectation-maximization algorithm using c programming language. psmix is mainly based on the methods proposed in tang et al. and liu et al.. three models are discussed in full detail in. the second one is equivalent to the model proposed in tang et al.. the first model is a special case of the second one. in tang et al. the method itself has been fully assessed by simulation studies.  we used two real datasets from rosenberg et al. and one simulated dataset from tang et al. to demonstrate the functionality of psmix. one real dataset contains two american populations, pima and surui with and individuals, respectively; the other contains two european populations, sardinian and russian with and individuals, respectively. the simulated data set contains individuals from each of the two ancestral populations, and individuals from the admixed population. the true individual admixture values of the admixed individuals are also available. to evaluate the efficiency of psmix, we randomly selected markers from the pima-surui dataset with no missing values and tried the four models available in structure. burnin length and number of mcmc replications after burnin were both set to be in the analyses. the time needed for each run of structure increased almost linearly with the increase of number of clusters. on our pc with pentium iii mhz cpu and mb sdram, when k = about two and a half minutes were needed for each run of structure. for all psmix runs, we set the stopping criterion to be that the parameter difference <10- between consecutive iterations, or steps, whichever was reached first. for the same pima-surui data with markers, each run of psmix needed about seconds. to evaluate the accuracy of psmix, we compared the results of psmix with those of structure. figure gives a sample run for the pima-surui dataset using only the first markers. for the pima-surui dataset using the first markers from the original data, the correlation coefficient between the results of psmix and structure was greater than. for the sardinian-russian dataset, when all markers were used, both structure and psmix had one individual misclustered. the correlation coefficient between the results was. the two methods produced very similar results. this is consistent with the findings in tang et al.. figure shows the results of structure, l-pop, and psmix. we can see that the results of psmix are much closer to those of structure. to evaluate the performance of psmix, we also used a simulated data set exhibiting population admixture. from figure we can see the psmix performs pretty well and the results are almost identical to those from structure. discussion we have implemented a likelihood based method of population structure inference into an efficient r package, psmix. psmix can be used in population genetics and disease gene mapping, wherever population stratification or individual admixture is needed to be estimated from genetic markers. compared with other available similar programs, psmix has several advantages. first, it is computationally efficient and provides similar accuracy under realistic situations. and thus the confidence intervals of the estimates can be constructed via resampling methods, e.g., the bootstrap method. second, as shown in tang et al., it performs a little better under some conditions involving a small number of ancestors and markers. we note that l-pop is also computationally efficient. however, it is not clear if l-pop can perform better under such conditions. third, it is very flexible. it is likelihood based and can be easily incorporated into study designs, such as marker choice. the program is implemented as a public r package and can be easily extended and incorporated into other packages. this is an advantage of psmix over structure and l-pop, which has only executable programs. we would like to note that the examples used in this work are mainly for the purpose of demonstrating the r package, not for the purpose of the assessing the underlying method. please refer to tang et al. for a detailed assessment of the methodology. in our simulation and application to real data, psmix and structure gave very similar results. this is not surprising because estimating parameters via maximum likelihood and maximum a posterior with flat prior is formally strictly similar, where psmix belongs to the former and structure belongs to the latter. many studies have been performed to assess the ability of structure in assigning individuals to their populations of origin using either real data or simulated data. however, very limited studies have been performed to assess the ability of structure in detecting the number of populations. recently, evanno et al. performed a systematic study on this issue using simulations. they simulated amplified fragment length polymorphism and microsatellite genetic data under three population structure models: the island model, a contact zone, and a hierarchical island model. their major finding is that the "log probability of data", an ad hoc criterion suggested by pritchard et al. for detecting the number of populations, does not provide a correct estimation of the number of populations most of the time. however, they found that another ad hoc statistic, which is based on the rate of change in the log probability of the data between successive numbers of populations, can accurately detect the uppermost hierarchical level of structure. they also found some other factors that can affect the detection of the number of populations. these findings are important and useful in that with the increasing usage of structure, they provide guidance on how to use structure to detect the number of populations. however, psmix does not directly detect the number of populations in this version. due to its computation efficiency, model selection methods such as akaike information criterion, bayesian information criterion, and even more general, penalized likelihood based methods can be used for this purpose. the findings of evanno et al. may be incorporated into psmix as well. this is one of our future works. em approach and bayesian mcmc approach have their own advantages and disadvantages. they both can trap in local modes, although theoretically speaking, bayesian mcmc approach can converge to the true value eventually, maybe after an unrealistic long time. however, the bayesian mcmc approach, in addition, has the label switching problem. two authors of the paper where the method of structure was proposed mentioned in other papers on methods to deal with this problem. although this issue is believed to be well addressed by structure, it does make the bayesian mcmc approach more complicated. however, this topic is beyond the scope of this work. from the users' point of view, they only see the computation efficiency and stability of the methods. we think that it may be necessary to explicitly explain some details about the models mentioned in this work. first, the orientation of tang et al. is different from that of structure, l-pop, and liu et al.. the goal of the former was to estimate individual admixture for the admixed individuals. the original focus of the latter was to "identify discrete clusters roughly corresponding to subpopulations". structure, l-pop, and liu et al. use methods for clustering, although they "can also be applied to an admixture model". so initially, tang et al. faced a population that is currently in hardy-weinberg equilibrium, but was created as the result of admixture at some point in the past. however, as emphasized in tang et al., the problem may not be identifiable without the inclusion of pseudo-ancestors who are proxies of the true pure ancestry. here the nonidentifiablity issue is related to the problem, and by no means pertains to the method. in other words, the nonidentifiablity issue exists and has nothing to do with the statistical methods to be used, if pseudo-ancestors are not included. therefore, the actual data tang et al. dealt with consist of "i individuals from the admixed group, as well as ik subjects from each of the k ancestral populations", that is, a stratified "pooled" population. so the actual data all these methods deal with are the same in the sense that the data consist of stratified populations within which hardy-weinberg equilibrium holds. one major difference is that tang et al. only focus on the individual admixture of the people in the admixed population. facing the same data, the method in tang et al. is for clustering as well, in spirit. they included pseudo-ancestors and used clustering method in order to estimate individual admixture. in other words, all the aforementioned methods are for population stratification, and can be applied to estimate individual admixture. thus the comparisons made in this work are appropriate. we also want to emphasize here the importance of inclusion of ancestral populations or their surrogates when individual admixture is needed; otherwise the problem may not be identifiable no matter what method to use.  in summary, we have implemented a new, likelihood based method for inference of population stratification and individual admixture which is available as a public r package. although the package has several advantages over its peers, we strongly suggest that the users use different software in their analysis. if the results from these software are consistent; this may provide more support for the results; if the results are not consistent, further investigation is needed. a potential limitation is the assumption of independence among markers behind psmix, which will be addressed in future versions of psmix. availability and requirements project name: psmix project home page: operating system: ms windows, linux, mac programming language: c, r other requirements: r or higher license: gpl any restrictions to use by non-academics: none authors' contributions bw participated in the design of the study, implemented psmix, and helped to draft the manuscript; nl participated in the design of the study, performed the analysis, and drafted the manuscript; hz conceived the study, participated in its design and helped to draft the manuscript. all authors read and approved the final manuscript. 
inference of population stratification and individual admixture from genetic markers is an integrative part of a study in diverse situations, such as association mapping and evolutionary studies. we have developed psmix, an r package based on maximum likelihood method using expectation-maximization algorithm, for inference of population stratification and individual admixture. bayesian methods have been proposed for population stratification and admixture inference using multilocus genotypes and widely used in practice. compared with software based on bayesian methods, psmix has similar accuracy, but more efficient computations.
 inference of population stratification and individual admixture from genetic markers is an integrative part of a study in diverse situations, such as association mapping and evolutionary studies. bayesian methods have been proposed for population stratification and admixture inference using multilocus genotypes and widely used in practice. however, these bayesian methods demand intensive computation resources and may run into convergence problem in markov chain monte carlo based posterior samplings.  we have developed psmix, an r package based on maximum likelihood method using expectation-maximization algorithm, for inference of population stratification and individual admixture.  compared with software based on bayesian methods, psmix has similar accuracy, but more efficient computations. psmix and its supplemental documents are freely available at. 