A greedier approach for finding tag SNPs.
BACKGROUND
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.


BACKGROUND
The program is available upon request.
Chang
Chia-Jung
CJ
Department of Computer Science and Information Engineering, National Taiwan University Taipei, Taiwan.
Huang
Yao-Ting
YT
Chao
Kun-Mao
KM
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods*; D020224:Expressed Sequence Tags; D014644:Genetic Variation / Q000235:genetics; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*