A greedier approach for finding tag SNPs

• Published in: Bioinformatics 2006-03, Vol.22 (6), p.685-691
• Main Authors: Chang, Chia-Jung, Huang, Yao-Ting, Chao, Kun-Mao
• Format: Article
• Language: English
• Subjects: Algorithms; Biological and medical sciences; Chromosome Mapping - methods; DNA Mutational Analysis - methods; Expressed Sequence Tags; Fundamental and applied biological sciences. Psychology; General aspects; Genetic Variation - genetics; Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects); Polymorphism, Single Nucleotide - genetics; Sequence Alignment - methods; Sequence Analysis, DNA - methods
• ISSN: 1367-4803; 1460-2059; 1367-4811
• DOI: 10.1093/bioinformatics/btk035

Motivation: Recent studies have shown that a small subset of Single Nucleotide Polymorphisms (SNPs) (called tag SNPs) is sufficient to capture the haplotype patterns in a high linkage disequilibrium region. To find the minimum set of tag SNPs, exact algorithms for finding the optimal solution could take exponential time. On the other hand, approximation algorithms are more efficient but may fail to find the optimal solution. Results: We propose a hybrid method that combines the ideas of the branch-and-bound method and the greedy algorithm. This method explores larger solution space to obtain a better solution than a traditional greedy algorithm. It also allows the user to adjust the efficiency of the program and quality of solutions. This algorithm has been implemented and tested on a variety of simulated and biological data. The experimental results indicate that our program can find better solutions than previous methods. This approach is quite general since it can be used to adapt other greedy algorithms to solve their corresponding problems. Availability: The program is available upon request. Contact:[e-mail]