title: A greedier approach for finding tag SNPs.
abstract: 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.
authors.affiliation: Department of Computer Science and Information Engineering, National Taiwan University Taipei, Taiwan.
authors.forename: Chia-Jung
authors.initials: CJ
authors.lastname: Chang
authors.forename: Yao-Ting
authors.initials: YT
authors.lastname: Huang
authors.forename: Kun-Mao
authors.initials: KM
authors.lastname: Chao
mesh_terms: 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*