Chang Chia-Jung, Huang Yao-Ting, Chao Kun-Mao
Department of Computer Science and Information Engineering, National Taiwan University Taipei, Taiwan.
Bioinformatics. 2006 Mar 15;22(6):685-91. doi: 10.1093/bioinformatics/btk035. Epub 2006 Jan 10.
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.
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.
The program is available upon request.
最近的研究表明，一小部分单核苷酸多态性（SNP）（称为标签SNP）足以捕捉高连锁不平衡区域中的单倍型模式。为了找到标签SNP的最小集合，用于寻找最优解的精确算法可能需要指数时间。另一方面，近似算法效率更高，但可能无法找到最优解。
我们提出了一种结合分支定界法和贪婪算法思想的混合方法。该方法探索了比传统贪婪算法更大的解空间，以获得更好的解。它还允许用户调整程序的效率和解决方案的质量。该算法已在各种模拟数据和生物数据上实现并进行了测试。实验结果表明，我们的程序能够找到比以前的方法更好的解。这种方法非常通用，因为它可用于调整其他贪婪算法以解决其相应问题。
可根据要求提供该程序。
