| 个体单体型问题参数化算法研究 |
| |
| 引用本文： | 谢民主,陈建二,王建新. 个体单体型问题参数化算法研究[J]. 计算机学报, 2009, 32(8). DOI: 10.3724/SP.J.1016.2009.01637 |
| |
| 作者姓名： | 谢民主 陈建二 王建新 |
| |
| 作者单位： | 1. 中南大学信息科学与工程学院,长沙,410083;湖南师范大学物理与信息科学学院,长沙,410081
2. 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金，国家"九七三"重点基础研究发展规划前期研究专项基金，长江学者和创新团队发展计划，湖南省自然科学基金，中国博士后科学基金及中南大学博士后科学基金 |
| |
| 摘 要： | 个体单体型问题指如何利用个体DNA测序片断数据,根据不同的优化准则确定该个体单体型的计算问题.因为技术上的限制,DNA测序实验中能直接测定的片断长度是有限的,一个片断所覆盖的最大SNP位点数k1通常小于10;出于时间和金钱的考虑,覆盖一个SNP位点的最大片断数k2也不是很大,通常约为10左右;与要测定的单体型SNP位点总数,n及所测序的DNA片断总数m相比,k1和k2均很小.在此基础上,文中对个体单体型问题最少SNP位点删除MSR和最少片段删除MFR模型进行了参数化,提出了时间复杂度分别为O(nk1k2+mlogm+mk1)和O(mk22+mlogm+nk2)求解无空隙MSR和MFR的精确算法.和Bafna等提出的时间复杂度为O(mn2)和O(m2n+m2)的精确算法相比,文中的算法效率提高了很多,具有较高的实用价值.
|
| 关 键 词： | 单核苷酸多态性 单体型 参数化算法 最少SNP位点删除 最少片断删除 |
Research on Parameterized Algorithms of the Individual Haplotyping Problem |
| |
| XIE Min-Zhu,CHEN Jian-Er,WANG Jian-Xin. Research on Parameterized Algorithms of the Individual Haplotyping Problem[J]. Chinese Journal of Computers, 2009, 32(8). DOI: 10.3724/SP.J.1016.2009.01637 |
| |
| Authors: | XIE Min-Zhu CHEN Jian-Er WANG Jian-Xin |
| |
| Affiliation: | School of Information Science and Engineering;Central South University;Changsha 410083;College of Physics and Information Science;Hunan Normal University;Changsha 410081 |
| |
| Abstract: | The Individual Haplotyping Problem is the computing problem of inducing an individual's haplotypes based on several optimal criteria from one's DNA sequence fragment data.Limited by current sequencing techniques,the maximum length of a fragment sequenced directly by DNA sequencers is not large,and the maximum number k1 of SNP sites covered by a fragment is usually smaller than 10.In order to save money and time,the maximum number k2 of fragments covering a SNP site is also small and about 10.Compared with t... |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
