AIM-SNPtag: A computationally efficient approach for developing ancestry-informative SNP panels

Inferring an individual's ancestry or group membership using a small set of highly informative genetic markers is very useful in forensic and medical genetics. However, given the huge amount of SNP data available from a diverse of populations, it is challenging to develop informative panels by exhaustively searching for all possible SNP combinations. In this study, we formulate it as an algorithm problem of selecting an optimal set of SNPs that maximizes the inference accuracy while minimizes the set size. Built on this conception, we develop a computational approach that is capable of constructing ancestry informative panels from multi-population genome-wide SNP data efficiently. We evaluated the performance of the method by comparing the panel size and membership inference accuracy of the constructed SNP panels to panels selected through empirical procedures in previous studies. For the membership inference of population groups including Asian, European, African, East Asian and Southeast Asian, a 36-SNP panel developed by our approach has an overall accuracy of 99.07%, and a 21-SNP subset of the panel has an overall accuracy of 95.36%. In comparison, an existing panel requires 74 SNPs to achieve an accuracy of 94.14% on the same set of population groups. We further apply the method to four subpopulations within Europe (Finnish, British, Spanish and Italian); a 175-SNP panel can discriminate individuals of those European subpopulations with an accuracy of 99.36%, of which a 68-SNP subset can achieve an accuracy of 95.07%. We expect our method to be a useful tool for constructing ancestry informative markers in forensic genetics.