<p><em>structure</em> 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.</p>

<p>Here's the description I have about <em>structure</em> from <a href="http://researcharchive.vuw.ac.nz/handle/10063/1987" rel="nofollow noreferrer">my PhD thesis</a>. It might be a bit dated now, but I expect most of it is still applicable:</p>

<p>A clustering program called <em>structure</em> was created by <a href="http://www.genetics.org/content/164/4/1567.full" rel="nofollow noreferrer">Falush et al. (2003)</a> that is used to determine population structure using a set of unlinked genotypes. The expected use case for <em>structure</em> 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.</p>

<p>The main benefit of using <em>structure</em> 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).</p>

<p>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.</p>

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

<ol>
<li>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).</li>
<li>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).</li>
</ol>

<p>In more simple terms, the steps are similar to the following statements:</p>

<ol>
<li>these populations probably have <em>this</em> allele frequency distribution
therefore...</li>
<li>these individuals probably came from <em>this</em> population</li>
</ol>

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

<p>The file that is output from <em>structure</em> 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 <a href="http://onlinelibrary.wiley.com/doi/10.1046/j.1471-8286.2003.00566.x/full" rel="nofollow noreferrer">(Rosenberg, 2004)</a>, a program that allows colour customisation and group re-ordering. For the purpose of this thesis, a custom R script, <code>snpchip2structure.R</code>, 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.</p>

CC BY-SA 3.0
2018-02-15T02:39:09.967Z
2018-02-15T11:44:44.920Z
2018-02-15T11:44:44.920Z
gringer
<p>If I were to run BAM/SAM files through a program like STRUCTURE, or ADMIXTURE described  <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3665925/" rel="nofollow noreferrer">here</a> how would they determine which individuals belong to what groups?</p>

<p>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?</p>

<sam><phylogenetics>
How do programs like STRUCTURE determine populations from alignments?
# How do programs like STRUCTURE determine populations from alignments?

(Asked by: username_0 on 2018-02-14)

If I were to run BAM/SAM files through a program like STRUCTURE, or ADMIXTURE described [here](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3665925/) 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?

**Tags:** sam, phylogenetics

---

## 1 answers

### Answer by username_1 on 2018-02-15. Score: 2 | Accepted answer

*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](http://researcharchive.vuw.ac.nz/handle/10063/1987). 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)](http://www.genetics.org/content/164/4/1567.full) 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)](http://onlinelibrary.wiley.com/doi/10.1046/j.1471-8286.2003.00566.x/full), 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.


---

