# How do programs like STRUCTURE determine populations from alignments?

If I were to run BAM/SAM files through a program like STRUCTURE, or ADMIXTURE described here how would they determine which individuals belong to what groups?

What part of the files would these programs use to determine which individuals belonged to different populations? I believe they do this via determining allele frequencies for each individual and then putting them into a population based on allele frequency, is the only criteria that they use comparison of allele frequencies between individuals?

structure works with SNP/genotype information, so won't work directly off BAM/SAM files. You would need to convert to VCF (e.g. using mpileup/vcftools), then process using something like PLINK to convert it into a format that STRUCTURE recognises.

Here's the description I have about structure from my PhD thesis. It might be a bit dated now, but I expect most of it is still applicable:

A clustering program called structure was created by Falush et al. (2003) that is used to determine population structure using a set of unlinked genotypes. The expected use case for structure is in the analysis of population structure, but it can also be useful for determining the utility of a given set of markers for categorising (or quantifying) a given trait.

The main benefit of using structure over other methods is that it is able to derive estimated ancestry coefficients from the data, rather than a discrete yes/no for each individual. This allows for the use of cutoff values for the assignment of individuals (useful for tweaking false positive and false negative rates in diagnostic tests), and a quantifiable value where a classification is not useful or does not make sense (as in the case of a continuous trait with high heritability such as height).

The program begins by assigning each individual to a given population. This can be either given in the input data as a ‘popinfo’ flag, or determined randomly by structure. After this, the program constructs a probability distribution for the data, considering the population assignments given, and uses that to estimate population allele frequencies. The program then constructs another probability distribution for these data, and uses that to estimate the population that each individual is likely to have originated from. This process is repeated many times (such a process is known as a random walk), and the underlying theory suggests that the progression of population assignments through the random walk process can be used as an approximation of the actual populations of origin for each individual.

The documentation included with structure describes the general algorithm for each iteration (of maybe hundreds of thousands of iterations) as follows:

1. Sample (population allele frequencies for iteration m) from the probability of (allele frequency) given (genotypes of sampled individuals) and (population of origin of individuals for iteration m − 1).
2. Sample (population of origin of individuals for iteration m) from the probability of (population of origin) given (genotypes of sampled individuals) and (allele frequencies for iteration m).

In more simple terms, the steps are similar to the following statements:

1. these populations probably have this allele frequency distribution therefore...
2. these individuals probably came from this population

The structure program is able to accommodate admixture into its model by considering the population of origin as a probability, rather than a single discrete value.

The file that is output from structure is a text file with individual identifiers and predicted ancestry coefficients (Q values). While the program does provide means to display these data graphically, the visual representation of data (including sorting) is better controlled using an external program. The most commonly used program is Noah Rosenberg’s distruct (Rosenberg, 2004), a program that allows colour customisation and group re-ordering. For the purpose of this thesis, a custom R script, snpchip2structure.R, has been designed which also allows selection of different sorting methods, a scatter plot for two populations, error bars, and a few additional features (see figure 1.7). More details about this script can be found in the programs directory of the supplementary CD for this thesis.