BAPS: Bayesian Analysis of Population Structure

Manual v. 4.14

This version improves the linkage clustering module by reducing the computation time by 50-90%, depending on the length and number of analyzed sequences.

NOTE: ANY INQUIRIES CONCERNING THE PROGRAM SHOULD BE SENT TO JUKKA CORANDER
Latest update of this manual on 25.04.2007

Jukka Corander, Pekka Marttinen, Jukka Sirén and Jing Tang

 Department of Mathematics, Åbo Akademi University, Finland

http://www.abo.fi/mnf/mate/jc/smack_index_eng.html

Table of contents:
Introduction
Basic software GUI features
Inputs for BAPS 4
Inputting the maximum number of populations, K
Clustering of individuals
BAPS format
GenePop format
Pre-processed data
Clustering of groups of individuals
BAPS format
GenePop format
Pre-processed data
Trained clustering
Spatial clustering
Clustering of linked molecular data
Admixture of individuals based on mixture clustering
Admixture based on pre-defined clustering
About results
Graphics
Numerical results in the output file for mixture clustering
Numerical results in the output file for admixture analysis
Installation
References

Introduction

BAPS 4 (Bayesian Analysis of Population Structure) is a program for Bayesian inference of the genetic structure in a population. BAPS 4 treats both the allele frequencies of the molecular markers (or nucleotide frequencies for DNA sequence data) and the number of genetically diverged groups in population as random variables. BAPS 4 contains all the functionality of BAPS 3.2, and introduces two new models for genetic clustering: a spatial model for genetic discontinuities in populations and a model for linked marker or sequence data.

With BAPS 4 you can cluster molecular data and perform admixture analyses. Genetic mixture analysis can be done either at: 

(1)	group level (typically corresponds to clustering of sample populations), or at 
(2)	individual level. 

In fact, in many applications with relatively sparse molecular data it is wise to do analyses at both these levels, when biologically relevant auxiliary information is available to define the groups before the mixture analysis (see Corander et al 2003, or Corander and Marttinen 2006, for further information). Both types of genetic mixture analyses can be done either by using a:

(1)	non-spatial, or 
(2)	spatial model, 

for genetic discontinuities in populations. The spatial model requires that coordinate data is available for the clustered units (groups or individuals), however, these may contain also missing values. In 'Trained clustering' you can make use of individuals whose origin is known, in order to find the best clustering of individuals with unknown origins. In ‘Clustering with linked loci’ a genetic mixture analysis is done either for haploid sequence data, phased diploid/tetraploid sequence data, or for linked marker data for which a single allele is recorded per locus. The latter can thus be e.g. dominant markers such as AFLPs for a diploid organism, or SNPs for a haploid organism.

Given the results from any of the models for genetic mixture analysis, or any given division of a set of individuals to a number of ‘Populations’, you can also do inference about admixture events. 

The different modules incorporated in BAPS 4 have been introduced in a number of scientific papers, and therefore, the following table provides guidance about which should be cited when publishing results produced with the software. As some of the papers are ‘in press’, the BAPS webpage will be updated with the detailed scientific citation information when such becomes available. 

In addition to the papers below, a mathematical derivation of the partition-based approach used in BAPS to learning genetic population structure from molecular data is given in the paper: Corander, J., Gyllenberg, M. and Koski, T. (2007). Random Partition models and Exchangeability for Bayesian Identification of Population Structure. Bulletin of Mathematical Biology, 69, 797-815.

Software module:	Scientific citation:	
Admixture analysis	Corander J, Marttinen, P. Bayesian identification of admixture events using multi-locus molecular markers. Molecular Ecology, 2006, 15, 2833-2843.	
Non-spatial genetic mixture analysis, including ‘Trained clustering’	Corander J, Marttinen P, Mäntyniemi S. Bayesian identification of stock mixtures from molecular marker data. Fishery Bulletin, 2006, 104, 550-558.	
Spatial genetic mixture analysis	Corander J, Sirén J, Arjas E. Bayesian Spatial Modelling of Genetic Population Structure. 2007. Computational Statistics. in press	
Genetic mixture analysis with sequences or linked loci	Corander J, Tang J. (2007). Bayesian analysis of population structure based on linked molecular information. Mathematical Biosciences, 205, 19-31.	
Earlier BAPS papers:	Corander, J., Waldmann, P. and M.J. Sillanpää. 2003. Bayesian analysis of genetic differentiation between populations. Genetics 163: 367-374.

Corander J, Waldmann P, Marttinen P, Sillanpää MJ (2004) BAPS 2: enhanced possibilities for the analysis of genetic population structure. Bioinformatics 20: 2363-2369.

The idea in BAPS 4 GUI is exactly the same as in BAPS 3. Any analysis is performed by clicking the corresponding button, and providing the necessary input to the algorithms by choosing certain files and by feeding values to any fields opened by the GUI. After the analysis, program writes the numerical results to the log-window and to a result file, if such has been specified by the user. Depending on situation, the program may also provide a visual representation of genetic mixture or admixture results (this is automatically done whenever possible, i.e. the number of clusters is not too extensive). The graphics can be saved and opened in the program using the internal format, but they can also be exported to a variety of different formats. 

Warning: To avoid system instability, if you wish to actively work simultaneously with BAPS and other Windows programs (like edit a Word document during the time BAPS is doing the estimation), you should explicitly give lower priority to BAPS4.exe process in the Windows Task Manager (press once ctrl-alt-del, choose Task manager, then Processes, and just right-click on the process BAPS4.exe, and choose Low priority). We recommend that you do this priority setup before you click on the analysis button. When BAPS is idle (meaning no estimation procedure is running), it doesn’t consume very much system resources, so you easily leave it open in the background.

Hint: We recommend that you check the “pre-processed data” option described in the data format section. This is a particularly useful time-saving option for analyses of large data sets. The pre-processed files are compatible between spatial and non-spatial mixture clustering modules, however, if you load a pre-processed data set without coordinates to the spatial clustering module, the program will ask for a coordinate file.

Contrary to BAPS 2, where a Markov Chain Monte Carlo (MCMC) algorithm is used for estimation, BAPS 4 uses stochastic optimization to infer the posterior mode of the genetic structure. This algorithm has in tests performed 100-1000 times faster than the MCMC approach to find an estimate with a comparable goodness-of-fit level. Also, the amount of RAM memory required by BAPS 4 is negligible compared to BAPS 2. 

Under certain circumstances it is useful to consider both BAPS 4 and BAPS 2 programs to investigate the population structure. For large data sets this is not always possible, since the memory and CPU time requirements by BAPS 2 may be too extensive. BAPS 2 is primarily useful (as compared to BAPS 3 & 4) only for groupwise mixture clustering based on very few markers (~1-5), as it allows a characterization of the posterior distribution over the clustering solutions in terms of the dendrogram (see BAPS 2 manual for the details). Goodness-of-fit levels of the results for any particular data are easily compared in terms of the “logml-values” (natural logarithm of the marginal likelihood of the data) provided for any particular clustering solution. Notice that you cannot compare “logmls” across different data sets. In BAPS 2, “logml” for the posterior mode (this is the partition associated with highest estimated posterior probability) may be obtained from the “View Chains”-window, by subtracting 10 from the absolute value in the “YMax” field (if Ymax = -1000, then “logml” for the posterior mode is -990). In BAPS 4, the “logml” is written to the log-window and to the output file (if you have defined such a file in the File-menu). 

Notice that the “logml” values are always negative, so that when two particular clusterings have “logmls” equal to -1950 and -1945, the latter clustering provides a better fit, and the Bayes factor for the latter against the former is exp(5) (exponential of their absolute difference), meaning that the latter is exp(5) times better than the former, as measured in the posterior probability.

Basic software GUI features

The are only two basic menus: File and Figures, and the additional menu: Help. The Help menu items only work in Windows environment. 

In the File menu you can either set or remove the text output file where the program writes the numerical results. Notice that when several analyses are performed without changing the output file, the new results are always appended after the old ones. 

An internal format (binary) clustering result file is produced each time you run a clustering and choose to save the results when the program asks you to (this file contains the numerical values needed e.g. in the admixture analysis). Notice that this does not refer to the output file specified in the File menu, where results are stored in text format. 

In the Figures menu you can open graphics saved earlier in the software’s internal format (different from BAPS 2 and 3), and also, you can produce a variety of plots of the clustering results. These graphics are explained in the result section of the manual. 

Inputs for BAPS 4

Here you find information about what the program expects as input when you click any of the analysis buttons. 

Inputting the maximum number of populations, K
In all clustering modules of the ‘Population mixture analysis’ you need to tell the program your opinion about the maximum number of genetically diverged groups, say K. In 'Trained clustering' K must naturally be greater or equal to the number of reference clusters. The prior distribution for clusterings is then either: (1) uniform in the space of clusterings having at most K clusters for the non-spatial model, or (2) non-uniform in the space of clusterings having at most K clusters for the spatial model, depending on the spatial pattern of the observed data. Generally, the larger the K, the longer the execution of the estimation algorithm will take. We recommend that you experiment with different values of K and run the analysis several times (it typically goes fairly fast), to see whether the results change noticeably (which you can always see by comparing their corresponding “logmls”). As an example, you might have a sample of 100 individuals genotyped at 10 microsatellite loci, and on the basis of your biological reasoning, you expect to find 3 divergent clusters. However, you might also have outlier individuals in the data, not representing any of these 3 groups, so a careful strategy would e.g. be to run the estimation with K = 5, K = 10, K =15. If K is set to be extremely large, e.g. close to the number of observed individuals, then the algorithm may easier get stuck to a local mode. Clearly, if K is too small, the “true” structure cannot be detected. If you get the estimated number of clusters equal to K, then you should try with a higher K, because otherwise the results can be misleading. 

In practice the easiest way to run the program several times with different K is to provide a vector of values when the program askes you for the maximum number of clusters. For example if you want to run the estimation with K=5, K=10, and K=15, the correct input would be: '5 10 15' (without ':s). 

Hint! You can fill as many K values into the input window as you wish, e.g. like two hundred. The input field simply shifts to the right when it becomes filled. So the input could look like: 
10 10 10 10 10 10 11 11 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 etc.
What the program does for each K value (even the replicates of the same value) is to find the optimal partitions with k ≤ K, it stores these internally, and the after all K values have been processed, it merges the stored results according to the logml values. Even if small k values are considered a priori possible, they can have extremely bad fit compared to the larger values, in which case they are ignored in the results. 

Starting from different values K is important also in the sense that K affects the initial assignment of the simulation and thus the possibility of finding only a local mode is reduced when simulation is started many times from different initial assignments. It makes sense even to start the simulation many times with the same K, since the optimization algorithm is stochastic and can therefore end up in different solutions in separate runs. If a vector of K values is provided, BAPS will write its output on the basis of the best solution that was found. Exactly like with Structure software, some caution with K is necessary, e.g. use of K=200 for a data set of 250 individuals would not in general be a wise strategy.

See also 'pre-processed data' option, which is very useful if you wish to run the program many times and you have a large data set whose pre-processing takes a long time.

Clustering of individuals
There are three alternative ways of providing input for BAPS 4 when you wish to do the clustering of individuals whose genotypes are known.

BAPS format: 
The data files should be plain ascii text files. The input file contains a data matrix. The columns of the matrix correspond to loci at which the individuals were observed. The rows of the matrix correspond to the individuals. There is an additional column in the right end of the matrix that contains on each row the index of the individual whose alleles are presented on the row. There can be more than one row per individual. For example if individuals are diploid, there should be two rows per each individual corresponding to two alleles that can be observed at each locus. 

Alleles can be indexed with any non-negative integer value. The indices of individuals, however, should start with 1 for the first individual and end with the value that corresponds to the total number of individuals. Missing allele at some locus is denoted by any negative integer, e.g. –999 or -9 (these are widely used).

If the sampling populations of the individuals are known, you can input them by giving two additional files: one containing the names of the populations, the other containing the indices of the first individuals of each sampling population.

Example:

Data file:
5	2	1	
7	2	1	
5	8	2	
3	9	2	
2	5	3	
-999	5	3	
5	-999	4	
2	3	4	
3	8	5	
2	5	5	

Name file:
American
European

Index file:
1
4

In this example we wish to cluster 5 diploid individuals. The first individual has alleles 5 and 7 at the first locus and so on. Individuals 1, 2, and 3 were sampled in America and individuals 4 and 5 in Europe.	■

GenePop format:
See http://wbiomed.curtin.edu.au/genepop/help_input.html for general information about genepop format. The data must obey strictly the rules mentioned in the referred page concerning punctuation and empty spaces. Otherwise BAPS may be behave unexpectedly. You can use both 2- and 3-digit allele codes, BAPS will investigate the format of the data and act accordingly. However, all allele codes in one data file must have the same number of digits. Note that when you use data that is in genepop format you always have to provide two alleles for each individual at each locus. If you wish to cluster haploid individuals you must mark the other allele of each individual at each locus as missing  (00 or 000). BAPS uses the labels of the first individuals of the populations as names for the populations.

Pre-processed data:
Before the simulation can start all data must be pre-processed by BAPS. For large data sets the pre-processing may take more than half an hour. If you wish to analyse such data many times starting from different initial assignments, it saves some time to save the data after pre-processing it once. Next time, instead of starting from the original data file, start with the pre-processed file that you previously saved.

Clustering of groups of individuals
There are three alternative ways of providing input for BAPS when you wish to do the clustering of groups of individuals.

BAPS format: 
The data file is almost similar to the data file used in clustering of individuals. The only difference is that instead of specifying the individual, the last column contains the index of the group that is the origin of the alleles on the particular row.

The names of the groups can be given in a separate file.

Example:

Data file:
5	2	1	
7	2	1	
5	8	1	
3	9	2	
2	5	2	
-999	5	3	
5	-999	4	
2	3	4	
3	8	4	
2	5	4	

Name file:
American
European
African
Asian

In this example we have data from four distinct groups. In the first group we have observed alleles 5, 7, and 5 at the first locus and so on. The name of first group (rows 1,2,3) is American, the name of the second group (rows 4,5) is European, the name of the third group (row 6) is African and the name of the fourth group (rows 7-10) is Asian.	   ■

GenePop format:
See GenePop format above in the clustering of individuals. The populations in the data define the groups to be clustered.

Pre-processed data:
Instead of starting from the original group level clustering data file, you can start with the pre-processed file that you have saved after once pre-processing the original data. Notice that here you should not use files pre-processed for the individual level clustering.

Trained clustering

In order to do the trained clustering of individuals you must provide two data files: one containing the reference individuals whose origins are known, the other containing the sampling units (individuals or groups of individuals) that you wish to cluster. Both files must be in GenePop format (see GenePop format in Clustering of Individuals above). Individuals in one population (separated by a word 'pop') in reference data file correspond to individuals from a single origin. In the other file the word pop separates the sampling units. Thus, if you wish to cluster unknown individuals one by one, you should write the word 'pop' above every line that specifies an individual in the sampling unit data file.

In both data files all individuals should be given names. These names will be needed by the program when the output is written

Example:

Reference data file:
--individuals with known origins--
loc1, loc2
pop
s1, 0307 0202
s2, 0303 0201
pop
r1, 0502 0401
r2, 0200 0404

File specifying the sampling units:
--sampling units--
loc1, loc2
pop
ind1, 0404 0304
pop
ind2, 0307 0202
ind3, 0303 0102
pop
ind4, 0505 0404

In this example we have reference data from two populations. Individuals 's1' and 's2' are representatives of the first and individuals 'r1' and 'r2' of the second reference population. We wish to cluster three sampling units. The first sampling unit consists of one individual 'ind1' only. The second sampling unit consists of individuals 'ind2' and 'ind3' and the third sampling units consists of a single individual 'ind4'. 

The rationale behind the use of sampling units is that, if there is some biologically relevant information available that tells us that individuals 'ind2' and 'ind3' must have the same, yet unknown origin, then by clustering them together we are able to increase the statistical power to detect the correct origin. The availability of such information is very species dependent, and its reliability must be determined by the user from case to case. If there is no relevant information for such pre-grouping of the data to be clustered, then every individual should be one sampling unit in the input data set. 	   ■

Spatial clustering

The input to the spatial clustering modules is otherwise exactly the same as in the above cases of ‘Clustering of individuals’ and ‘Clustering of groups of individuals’, except for the coordinate values that need to be given in a separate file. The coordinate file should be plain ascii with as many rows as there are individuals (‘Spatial clustering of individuals’) or groups (‘Spatial clustering of groups’) in the molecular data set. If the coordinates are missing for an individual or a group, this should be indicated by a corresponding line in the coordinate file containing two consecutive zeros. Two examples of data input to the spatial analysis using the BAPS data format are given below. 

The rationale of using spatial information is to assign a biologically relevant non-uniform prior distribution over the space of clustering solutions, which expects that underlying clusters are spatially smooth at least to some extent. This increases the power to correctly detect the underlying population structure and can be used to investigate the population structure also visually. When the molecular data are very extensive, the spatial and non-spatial clustering models are expected to yield highly similar results. The graphical output from the spatial analysis is explained in the About Results section below.

Example:

Data file:
5	2	1	
7	2	1	
5	8	2	
3	9	2	
2	5	3	
-999	5	3	
5	-999	4	
2	3	4	
3	8	5	
2	5	5	

Coordinate file:              
172	88	
155	96	
180	78	
0	0	
-18	81	

In this example we wish to cluster 5 diploid individuals. The first individual was sampled at (172, 88), the second at (155, 96) and so on. The sampling coordinates of the fourth individual are unknown.

Example:

Data file:
5	2	1	
7	2	1	
5	8	1	
3	9	2	
2	5	2	
-999	5	3	
5	-999	4	
2	3	4	
3	8	4	
2	5	4	

Coordinate file:              
172	88	
155	96	
0	0	
-18	81	

In this example we have data from four distinct groups. The sampling coordinates of each group are in the Coordinate file, except for the third group which coordinates are unknown.

Clustering of linked molecular data

Here the rationale of the analysis is the same as for the genetic mixture analysis using unlinked markers, except that the used Bayesian model accounts for dependences present between the “loci” (either marker loci or sites within aligned sequences). The outputs from this software module can be further used in the admixture module.

Four distinct options are available for data input: MLST-format, BAPS-numeric format, BAPS-sequence format, and pre-processed data. The MLST option is intended for sequence data for prokaryotic organisms, such that the number of genes used for clustering can be specified by the user. The BAPS format can be used for both analyzing sequence and linked molecular marker data. 

Warning! Since the statistical model for linked data is much more complicated than the model for independent molecular markers, it requires more memory and CPU time for the analysis. Thus, it may happen that for very large data sets and long sequences over many genes your computer runs out of memory. Due to the manner by which the operative system frees memory for computer processes, it may be necessary to close and restart BAPS between very extensive analyses, to avoid system instability.

An example of analyzing sequence data using the MLST data format:

Assume you have sequence data over 6 genes (Adk, Gyr, Hsp60, Mdh, Pgi, RecA) for a number of bacterial isolates. In accordance with the MLST database standard formatting, BAPS requires a profile ascii file where each isolate corresponds to a row. The first column (ST) is the identifier where the numbering should go linearly from 1 to #isolates. The integers in the column must be unique such that  no more than one isolate shares a same ST number. The second column provides a unique ID label for each isolate, which is used in the printing of the results. The column header could be either ‘Isolate’ or ‘Strain’.  BAPS requires that at least one of these two columns is present in the dataset, since they are both unambiguous descriptors for isolates (or strains). The third column (optional) provides a species or similar group name for the isolates. Presence of the IDs and species names helps the user to investigate the clustering results, so they are recommended. The remaining columns correspond to the genes for which there are aligned sequences available. An example of the contents of a profile file is given below (the header line specifying each column a user wants to include must be present). 

ST	Isolate	Species	Adk	GyrB	Hsp60	Mdh	Pgi	RecA
1	1A1	My. splendidone	1	1	1	1	1	1
2	1B1	A. dent		2	2	2	2	2	2
3	1B2	A. dent		3	3	3	3	3	3
4	1A5	D. gently		4	4	4	4	4	4
...

Hint! For most of the datasets provided by the Profiles database in mlst.net, the Isolate and Species columns are not included. Although BAPS can process such profiles directly, it is recommended that one creates the full profile as shown above. This can be easily done by searching the Isolate database using multiple criteria and exporting the resulting profile with all the header names checked. For instructions in using the Isolate database, see: http://pubmlst.org/software/database/mlstdbnet/manual/ 

Hint! As long as the header names are written according to the rules mentioned above, the order of the columns could be arbitrary. For example the profile below is also acceptable by BAPS:

Isolate	Adk	GyrB	Hsp60	Species	  Mdh	 Pgi	RecA	ST
IA1	       1     1      1   My.splendidone 1   1      1    1
IB1          2     2      2   A.dent         2   2      2    2
…

After loading the profile file to BAPS, program asks which species are to be included in the analysis. By clicking on the Select all –option, all rows of the data set are included. After this, a user has the possibility to choose a range of isolates (all or a subset of them). When the selection of isolates is completed (all isolates to be included are in the right hand side window), click OK. Then, a window for selecting the genes for the analysis appears. For each chosen gene, BAPS requires the user to input a corresponding Fasta file containing the aligned sequences for all included isolates. An example of the Fasta data for the two first isolates of our example profile file is given below. The formatting of the name field for each sequence depends on both the gene name and the strain ID, i.e. this should equal: >”Gene name”-“ST”. The STs are denoted as integers (see above). Missing nucleotides in the sequence are by default denoted by the question mark (“?”) and sequence gaps denoted by the dash symbol (“-“). However, both incomplete information types will be decoded as the same after the data is loaded and are thus not distinguishable. For convenience it is possible to use either of  the two symbols to denote any unknown bases. Notice also that all loaded sequences within a single gene should be of equal length (aligned). 

>RecA-1
CTAACGCTTGAGCTTATTGCTGCAGCGCAGAAAGTAGGTAAAACGTGTGCATTCGTTGATGCGGAACACGCACTTGACCCTATCTACGCTCAAAAGCTTGGTGTTGATATTGACGCTTTGCTTGTATCTCAACCTGATACGGGTGAACAAGCTCTAGAAATTTGTGATGCACTGGCTCGTTCAGGTGCTATCGATGTTCTTGTTATTGACTCGGTTGCTGCACTAACACCT-AGCTGAGATCGA-GGCGAAATGGGCGATAGCCACATG-GTCT--AGCACGTATGCTTTCTCAAGCAATGCGTAAGCTAACAGGTAACCTTAAGCAGTCTAACTGTATGGCTATCTTCATTAACCAAATTCGTATGAAAATTGGTGTAATGTTCGGTAAC
>RecA-2
CTAACGCTTGAGCTTATTGCTGCAGCACAGAAAGTGGGCAAAACGTGTGCATTCGTCGATGCCGAGCACGCACTAGACCCTATC-ACGCTCAAAAGTTGGGTGTTGATATCGACG-TTTGCTTGTGTCTCAACCAGA-ACAGGCGAAAAGCTCTAGAAATTTGTGATGCACTGGCTCGTTCAGGTGCTATCGATGTTCTTGTTATTGACTCAGTAGCAGCACTAACACCTAAAGCAGAAATCGAAGGCGAAATGGGCGATAGCCACATGGGTCTTCAAGCACGTATGCTTTCTCAAGCAATGCGTAAGCTAACAGGTAACCTTAAGCAGTCTAACTGTATGGCTATCTTCATTAACCAAATTCGTATGAAAATTGGTGTGATGTTTGGTAAC
...

After all the data have been provided for BAPS, it starts preprocessing the files. We recommend that you save the pre-processed data by answering Yes to the question, since this saves a lot of time in repeated analyses of the same data set. BAPS will ask the user to specify the linkage model, and for sequence type data it will be mostly relevant to use the Codon linkage model. After the linkage model is specified, BAPS asks whether to save the fully pre-processed data (again we recommend the user to do this). This question is raised because the chosen linkage model will affect the internal data formatting depending on the eventual presence of missing values. When running repeated analyses with the same data, the user can load the fully pre-processed data set by using the ‘Pre-processed’ option when clicking on ‘Clustering with linked loci’. The final option is to choose the prior upper bound K by typically inserting a range of values into the window. For details on this see the ‘Inputting the maximum number of populations, K’ section in the beginning of this manual. When the K-values have been given, BAPS starts to cluster the data, and when ready, prints the results to an output file (if this has been specified). After the clustering, BAPS asks whether the results should be stored using the internal format. This option is useful, as it enables investigation of putative horizontal gene transfer events using the admixture module.

An example of analyzing sequence data using the BAPS data format:

When the BAPS data format is used, the sequence data should be formatted either: (1) as haploid marker data for the other clustering modules (see the previous sections of this manual), which corresponds to a single data row per individual, or (2) as diploid marker data which is phased within each considered gene, which corresponds to two rows of data per individual, or (3) as tetraploid marker data which is phased within each considered gene, which corresponds to four rows of data per individual. 

Notice that in contrast to the MLST format you need under the BAPS format to concatenate the sequences from all considered genes into a single one, and tell the program about the gene boundaries in a separate file (see below).

You can either use a numeric data input format or a direct sequence (character) based format. The numeric format is obtained by replacing each of A,C,G,T with a unique integer, and by replacing the eventual dashes with a negative integer such as ‘-999’. Then a single data row for an individual, say 110, could look like:

65    65    67    67    71    -999    84  110

This corresponds to the underlying sequence AACCG-T. 

If you use the sequence data format, the 8 first rows of the data matrix, e.g. for tetraploid individuals will simply look like:

CTAACGCTTGAGCTTATTGCTGCAGCGCAGAAAGTAGGTAAAACGTGTGCATTCGTTGATGCGGAA 1
GCACTTGACCCTATCTACGCTCAAAAGCTTGGTGTTGATATTGACGCTTTGCTTGTATCTCAACCT 1
GATACGGGTGAACAAGCTCTAGAAATTTGTGATGCACTGGCTCGTTCAGGTGCTATCGATGTTCTT 1
GTTATTGACTCGGTTGCTGCACTAACACCT-AGCTGAGATCGA-GGCGAAATGGGCGATAGCCACA 1
TATCTAC--GAGCTTATTGCTGCAGCGCAGAAAGTAGGTAAAACGTGTGCATTCGTTGATGCGGAA 2
GCACTTGACCCTATCTACGCTCAAAAGCTTGGTGTTGATATTGACGCTTTGCTTGTATCTCAACCT 2
GATACGGGTGAACAAGCTCTAGAAATTTGTGATGCACTGGCTCGTTCAGGTGCTATCGATGTTCTT 2
GTTATCTAC--GGTTGCTGCACTAACACCT-AGCTGAGATCGA-GGCGAAATGGGCGATAGCCACA 2
...

Notice that there must be a space between the last elememt of the concatenated sequence and the individual index.
 
In the BAPS format it is also necessary to tell the program about the gene boundaries. This is done by providing a separate file where the number of rows equals the number of genes. At each row, the integers refer to those columns of the data matrix that correspond to the specific gene. Additional zeros are used to fill the rows to have an equal number of columns. As an example, the “linkage map” file could look like:

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 0
20 21 22 23 24 25 26 27 0 0

In this case there are three genes, the first corresponding to the columns 1-10, the second to columns 11-19, and the third to columns 20-27 in the data matrix. The additional zeros result in a matrix having an equal number of columns for each row. This type of data can be loaded to the ‘Clustering with linked loci’ by choosing BAPS format, and then using the ‘Codon linkage model’.

An example of analyzing linked molecular marker data using the BAPS data format:

Linked marker data should be formatted as haploid marker data for the other clustering modules (see the previous sections of this manual). The loci representing the same linkage group should be ordered linearly in accordance with the previous example concerning representation of sequences over a number of genes. Thus, for marker data each “gene” in the previous example should be replaced by a linkage group, and the other aspects of the formatting are kept equal. The “linkage map” file for three linkage groups could look like:

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 0
20 21 22 23 24 25 26 27 0 0

In this case the loci 1-10 in the data file represent the first linkage group, the loci 11-19 the second, and loci 20-27 the third linkage group. This type of data can be loaded to the ‘Clustering with linked loci’ by choosing BAPS format, and then using the ‘Linear linkage model’.

Admixture of individuals based on mixture clustering

The input file for admixture analysis under this option is the binary result file of mixture clustering (saved by the user at the end of any mixture analysis module). Notice that this is not the same thing as the ascii output file, where the results are written! All mixture clustering modules (non-spatial, trained, spatial, linkage) produce files that are compatible with the admixture module. To do admixture inference based on some highly probable mixture clustering solution other than just the mode saved by the program by default, see the next section of the manual! 

After mixture clustering analysis has finished you have an opportunity to save the result file in order to use it later for reproducing graphics and admixture analysis. If you used group level mixture clustering, BAPS will need to know how many rows from one individual are presented in the data. This will be asked from you before the saving is done. It is on user’s responsibility to make sure that the original data really contained the given number of rows per individual.

Before the admixture analysis can start you will be requested to input the minimum size of a population that will be taken into account when admixture is estimated. BAPS will then remove individuals who belong to a cluster whose size is less than the given number. The removed outlier individuals are displayed on the screen. 

In BAPS 4 you will also be asked the following things: 1) the number of iterations that are used to estimate the admixture coefficients for the individuals, 2) the number of reference individuals from each population, 3) the number of iterations that are used to estimate the admixture coefficients for the reference individuals. These three things affect the accuracy of the estimation. The first input determines the number of times the individuals in the data are analyzed using different simulated allele frequencies. The higher this input is, the better the uncertainty in the allele frequencies is taken into account. A good value would be for instance 100. For really extensive data sets lower values can be used according to time available for the analysis.  The second and the third input are needed in simulation and estimation of reference individuals. These individuals are used to estimate the noise. Good value for the number of reference individuals from one population would be for instance 200. Because the accuracy of admixture coefficients for the reference individuals is not of great importance, the number of iterations used to analyze these individuals can be much lower than what was used in the analysis of the individuals in the data. Reasonable values would be for instance somewhere between 5 and 20. It is usually a good idea to first test with small inputs to see how long the analysis takes and then do a re-analysis using higher values. 

Admixture based on pre-defined clustering

If the user has a good idea of how the individuals should be clustered, the admixture analysis can be done on the basis of a partition of individuals given by the user. This option provides also possibility to do admixture inference using other mixture clustering partitions than just the mode stored by default in the result file. For instance, assume the mixture clustering analysis indicates two solutions with high posterior probabilities, say one with P(k = 5) = .6 and the other with P(k = 6) = .4. In the mixture analysis the solution with five clusters has the highest probability, so it will be stored by default. However, you can do the admixture inference for the six cluster solution by creating an input data file where the ‘sample populations’ correspond to the six clusters indicated by the alternative mixture clustering result, and then running the admixture analysis option based on pre-defined clusters. Below we explain how to format such an input file.

In this module there are again two alternatives for providing the input for the program: BAPS and GenePop formats. If you use BAPS format, the input files are exactly similar to those used in the clustering of individuals. However, you also have to provide an additional file that contains the partition of the individuals. The partition file contains as many rows as there are individuals in the data. On each row there is an index identifying the cluster to which the individual belongs. The indices of the clusters must range from 1 to the total number of clusters. If the Genepop format is used, the input file is again similar to that used in the clustering of individuals. However, here the populations of individuals in the data (as separated by the word ‘pop’) are used to define the partition of individuals on which the admixture analysis will be based, instead of defining the sampling populations, as in ‘clustering of individuals’.

It is also possible to estimate the admixture of individuals with respect to different origins even if the placing of those particular individuals in different clusters is not known, and thus they do not contribute to allele frequencies of any particular population. As an example, suppose that you have two groups of individuals from two different origins and a third group of individuals who are known to be admixed from the known two origins. Now you wish to know the admixture proportions of the individuals in the third group. To do this kind of analysis in BAPS format you only have to mark the cluster (in partition file) of those individuals who are not pre assigned to any cluster as -1. In GenePop format the analysis is as easy. You just add an extra population in the end of the data file that specifies the individuals that have not been pre-assigned to clusters. Before the analysis starts the program will ask you if the last population in the data file will be used to define one more cluster with respect to which admixture proportions will be estimated, or if the last population consists of individuals who do not contribute to allele frequencies of any cluster. In order to this kind of admixture analysis being reasonable you should make sure that two prerequisites are met: first, all those populations who contribute to the genetic structure of individuals whose origin is not known, are present in the data. Second, all clusters given by the user really are genetically diverged. This can be tested by doing the mixture analysis with ‘clustering of individuals’ first.

As in the admixture analysis based on mixture clustering, you will also now be asked for the minimum size of a population that will be taken into account when admixture is estimated. In BAPS 4 you will also have to input the values that determine the numbers of iterations and the number of reference individuals. (see: Admixture based on mixture clustering. )

Example:

Data file:
5	2	1	
7	2	1	
5	8	2	
3	9	2	
2	5	3	
-999	5	3	
5	-999	4	
2	3	4	
3	8	5	
2	5	5	

Partition file:
1
1
-1
2
2

Name file:
American
European

Index file:
1
4

In this data there are exactly the same five individuals as in the example for clustering of individuals (Data file, Name file, and Index file are exactly the same). First two individuals are assumed to form one cluster whose ID label is 1. Individuals 4 and 5 form the second cluster (ID label 2). The admixture analysis is based on the allele frequencies computed on the basis of these two clusters. Individual number 3 is known to be admixed from the two given origins. However individual 3 is not pre- assigned to either cluster (-1 in partition file) and thus does not contribute to allele frequencies of either cluster.

About results

Graphics

The mixture clustering graphical output (colored partition of the clustered units) is automatically produced when there are at most 30 clusters. This output is also available from Figures menu as the View Partition –option. Each cluster is assigned a unique color in the graphic, but the color ordering is arbitrary, so you cannot compare colors between analyses. Each “sampling unit” (an individual or a group) that was clustered, is represented by a vertical bar having the color corresponding to the cluster where it was placed. Width of the bars depends on how many of them need to be drawn. If the names of the sampled populations have been provided to the program (see the input format section), these are printed below the colored bars to denote the sample origins. The names appear in the same order as in the data, and are printed in the middle of the set of bars representing the particular sample population. In 'Trained clustering' result picture the individuals are in such order that first are the reference individuals with known origins and after them come all other individuals.

The admixture clustering graphical output is also automatically produced when there are at most 30 clusters. Each cluster is assigned a unique color in the graphic, but the color ordering is arbitrary between analyses. Notice, that here every vertical colored bar necessarily corresponds to an individual, in the same order as in the original data provided by the user. The vertical bars are split into several colors when there is evidence for the admixture, such that each color corresponds to an ancestral source (a cluster), and the proportion of a particular color in the vertical bar corresponds to the proportion of the genome estimated to be represented by that source. A graphical tool for optimizing the admixture graphs for visual clarity is included in the software version 4.14. 

Voronoi tessellations are produced by the spatial clustering module when there are at most 30 clusters in the data (also accessible through the Figures menu). A cell of the tessellation corresponds to the physical neighborhood of an observed data point, and is colored according to the cluster membership. A graphical 3D-representation of the local posterior uncertainty in the estimated tessellation is available from the Figures menu as ‘Local uncertainty’.

For the non-spatial clustering module there is also an option of displaying the results in a spatial plot when sample coordinates of the analyzed data are available. When you choose Plot coordinates from the Figures menu, program asks you to specify a file containing the clustering results in the internal format (clearly you need to do the clustering first) and a text file containing the coordinates for each clustered “sampling unit”. The coordinates should be in a text file where each row specifies two numbers, the X- and Y-coordinate for the corresponding “sampling unit”. The coordinates should be in the same order as the “sampling units are in the original data set you gave as the clustering input to the program. If any coordinates are missing, please use a row with two zeros to denote that. In the 2D spatial plot, BAPS writes the cluster ID labels at corresponding coordinates. 

Numerical results in the output file for mixture clustering:

An example of the result file for individual level clustering is given below. The reported changes in “logml” if individual i is moved to group j, refer to how much worse the solution would become with the indicated change. The number is the logarithm of the Bayes factor, so that exp(“absolute value of the change”) tells how many times better the optimal partition (i.e. clustering) is. The value is zero for the cluster where the individual is in the optimal solution. Very small absolute values of the change (<2.3, see Kass and Raftery, 1995), indicate that the individual could possibly be allocated to the alternative cluster as well. For detailed explanation of Bayes factors, see Kass and Raftery (1995). The K-L divergence matrix refers to the estimated Kullback-Leibler divergence between the clusters. This can be used as a measure of the relative genetic distance between them, and it is the symmetric version of the divergence, calculated as an average over the loci (the divergence is not here normalized to fall between 0 and 1). For further information about the K-L divergence in the genetic context, see Corander et al. (2003), and Anderson and Thompson (2002). 

A list of sizes of ten best visited partitions with their log(ml) values is displayed. These values can be used to estimate the "correct" number of clusters. Also a posterior probability for the number of clusters is provided. This probability is based on the log(ml):s of the partitions that were visited during the current run. The probability is meant to be only a rough estimate. To get a better picture of the probabilities of different  numbers of clusters you should run the program many times giving a vector of values for K in the beginning (see: Inputting the maximum number of populations, K). Then the probability would be computed on the basis of best partitions that were visited during all the runs. Also, re-analysing the data with BAPS 2 is useful when there is much uncertainty concerning the number of clusters.

RESULTS OF INDIVIDUAL LEVEL MIXTURE ANALYSIS:
Data file: my_funny_data_set.mat
Number of clustered individuals: 42
Number of groups in optimal partition: 6
Log(marginal likelihood) of optimal partition: -1706.9897
 
Best Partition: 
Cluster 1: {7, 8, 31, 32, 33}
Cluster 2: {1, 2, 3, 6, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
           18, 19, 20, 24, 25, 26, 27, 28, 29, 30, 34, 35, 
           36}
Cluster 3: {4, 5}
Cluster 4: {37, 38, 39}
Cluster 5: {21, 22, 23}
Cluster 6: {40, 41, 42}

Changes in log(marginal likelihood) if individual i is moved to group j:
  ind      1        2        3        4        5        6        
    1:    -36.9       .0    -50.3    -68.4    -67.9   -106.4
    2:    -37.8       .0    -54.6    -72.8    -72.3   -107.9
.
.
.
   41:   -110.9   -167.0   -101.4   -103.9   -120.0       .0
   42:   -103.5   -164.5   -100.4   -102.3   -120.8       .0

KL-divergence matrix:
       1       2       3       4       5       6       
  1  
  2   0.311  
  3   0.419   0.516  
  4   0.543   0.632   0.355  
  5   0.598   0.683   0.394   0.505  
  6   0.710   1.021   0.667   0.677   0.807

Numerical results in the output file for admixture analysis:

An example of the result file for admixture analysis performed by BAPS 4 is given below. There were 5 clusters found by the clustering algorithm. The number in column i after the individual ID label, is the Bayesian posterior mean estimate of the proportion of the genome represented by the cluster i. Here, the first individual has estimated admixture coefficients .05, .87, and .08 for the 1st, 3rd and 4th clusters. The final column gives the p-value for the individual. This value tells the proportion of reference individuals simulated from the population in which the individual was originally clustered having the admixture coefficient to the cluster smaller than or equal to the individual. For instance the Bayesian p-value for the first individual in the example is 0.43 meaning that 43 per cent of the reference individuals simulated from population 3 (the population in which individual 1 was first clustered) had admixture coefficient to population 3 less than or equal to .87. Individuals having p-value larger than 0.05 are by default considered as having “non-significant” evidence for the admixture. Here, individual 1 has not “significant” admixture, whereas individuals 31, 561, and 562 have “significant” admixture. If a user wishes to apply a more stringent “significance” limit, one can simply use a lower threshold for the values in the final column.

RESULTS OF ADMIXTURE ANALYSIS BASED
ON MIXTURE CLUSTERING OF INDIVIDUALS
Data file: data_example_five_populations.mat
Number of individuals: 600
Results based on 50 simulations from posterior allele frequencies.

1:    0.05  0.00  0.87  0.08  0.00:  0.43
2:    0.00  0.02  0.84  0.05  0.09:  0.315
3:    0.05  0.04  0.91  0.00  0.00:  0.615
4:    0.00  0.00  0.99  0.01  0.00:  0.95
.
.
.
27:   0.01  0.00  0.92  0.02  0.05:  0.65
28:   0.09  0.00  0.88  0.03  0.00:  0.465
29:   0.07  0.00  0.77  0.16  0.00:  0.11
30:   0.00  0.00  0.98  0.01  0.01:  0.915
31:   0.12  0.00  0.72  0.16  0.00:  0.025
32:   0.11  0.00  0.89  0.00  0.00:  0.505
.
.
560:  0.99  0.01  0.00  0.00  0.00:  0.83
561:  0.49  0.00  0.00  0.51  0.00:  0
562:  0.37  0.00  0.04  0.59  0.00:  0.01
.
.
.

Installation

BAPS is currently available for Windows 2000/XP/Vista, Mac OS X and Linux operating systems. We are also developing a system based on a parallel computing architecture with a www-based GUI. 

The executable program can freely be downloaded from http://www.abo.fi/mnf/mate/jc/baps.html. To use the software, a runtime component available at the website (different versions for the three operating systems) has to be installed first. The runtime component can be installed anywhere in the operating system, EXCEPT under the Matlab path, if Matlab is installed on your computer. After the installation of the runtime component is finished, unzip the BAPS package to any folder, and the program is ready for use (except for Mac OS X and Linux, see further installation details on the BAPS website). 

References

Anderson, E. C. and Thompson, E. A. (2002) A model-based method for identifying species hybrids using multilocus genetic data. Genetics 160: 1217-1229.

Corander, J., Waldmann, P. and M.J. Sillanpää. 2003. Bayesian analysis of genetic 
differentiation between populations. Genetics 163: 367-374.

Corander J, Marttinen, P. 2006. Bayesian identification of admixture events using multi-locus molecular markers. Molecular Ecology, 15, 2833-2843.

Corander J, Waldmann P, Marttinen P, Sillanpää MJ (2004) BAPS 2: enhanced possibilities for the analysis of genetic population structure. Bioinformatics 20: 2363-2369.
Kass R, Raftery AE (1995) Bayes factors. J Amer Stat Assoc 90: 773-795.