【摘要】 本发明涉及计算机技术和生物技术，特别涉及一种基于DNA计算实现图顶点着色的技术，提供一种基于DNA计算实现图顶点着色的方法。基于DNA计算获得包含任意个顶点的图顶点着色方案。包括：将待着色图划分为至少两个子图；根据给定颜色种类，基于DNA计算获得每一个子图对应的顶点着色方案集合，每一种顶点着色方案中任意两个相邻顶点着不同颜色；基于DNA计算逐步合并各子图对应的顶点着色方案，获得所述待着色图的顶点着色方案集合。 【专利类型】发明授权 【申请人】北京大学 【申请人类型】学校 【申请人地址】100871 北京市海淀区颐和园路5号 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810085571.4 【申请日】2008-03-19 【申请年份】2008 【公开公告号】CN101256640B 【公开公告日】2010-06-02 【公开公告年份】2010 【授权公告号】CN101256640B 【授权公告日】2010-06-02 【授权公告年份】2010.0 【IPC分类号】G06N3/12; G06T15/00; C12Q1/68 【发明人】许进; 强小利; 张成; 杨静; 王淑栋; 刘向荣 【主权项内容】一种基于DNA计算实现的图顶点着色方法，其特征在于，包括：将待着色图划分为至少两个子图；分别确定各顶点可用的颜色集合，以及每个颜色集合中包含的颜色元素个数；对应每一个颜色元素生成互不相同的DNA序列，并为每两个标号连续且代表不同颜色的顶点生成DNA序列探针；采用PCR方法，分别根据每一个子图的DNA序列和DNA序列探针合成顶点着色方案的初始解空间；分别在每一个子图的初始解空间中删除非解并提取真解，每一个子图的所有真解构成的集合就是该子图的顶点着色方案集合；根据PCR方法，逐步两两合并具有桥点的子图的解，删除非解并提取真解，直到合并为一个完整的待着色图时获得所述待着色图的顶点着色方案集合。 【当前权利人】北京大学 【当前专利权人地址】北京市海淀区颐和园路5号 【专利权人类型】公立 【统一社会信用代码】12100000400002259P 【引证次数】2.0 【他引次数】2.0 【家族引证次数】2.0 【家族被引证次数】4
