Single-nucleotide polymorphism (SNP) markers are abundant on the human genome and can be used in fine mapping of genes. Although it is useful to choose markers spaced at regular intervals between two boundaries of a chromosomal region for mapping, it can be a difficult task since intervals vary from one residue to hundreds of thousands.

Our algorithms choose markers based on interval regularity within a genomic region containing a total of n markers, when given the desired number of select markers (m) or the desired interval (I). The solution set has a minimum variance of intervals or minimum sum of squared deviations from I. Although the number of all possible sets increases exponentially with respect to n, our algorithms cover them all with only O(n²) calculations and comparisons by inductively eliminating all redundancy.

These algorithms were implemented in a Windows program named CHOISS. It has a simple graphic interface and is equipped with several functions for convenience (automatic construction of an input file from a text form of NCBI Genbank contig data, graphic visualization of maps with total and chosen markers, etc.). It provides an option to choose between m- and I-value given cases. The program performs well on Windows 98, Me, 2000 and XP versions. It can be downloaded freely from this web page.

                           
Paper Published in Bioinformatics

     CHOISS for selection of single nucleotide polymorphism markers on interval regularity
     Soohyun Lee and Changwon Kang
     Bioinformatics Vol. 20, Issue 4, pp. 581-582 (March 1, 2004)
     (Bioinformatics Advance Access published online, January 22, 2004)
     DOI: 10.1093/bioinformatics/btg458

Supplementary information for the Bioinformatics paper

Contact: ckang@kaist.ac.kr