DNA并行计算中的B.pdf

第２９卷第５期 计 算 机 应 用 研 究 Ｖｏｌ２９Ｎｏ５ ２０１２年５月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｍａｙ２０１２ ＤＮＡ并行计算中的Ｂ树数据结构的设计与实现 １，２ ２ 邹超君 ，朱雅莉 （１．湖南大学信息科学与工程学院，长沙４１００８２；２．衡阳师范学院计算机科学系，湖南衡阳４２１００２） 摘　要：ＤＮＡ分子特性使得ＤＮＡ计算具有极大的存储密度和高度的计算并行性。不管何种计算模型，ＤＮＡ分 子的选择和ＤＮＡ编码都十分重要。提出了ＤＮＡ计算中的Ｂ树的数据结构设计方法。首先给出了Ｂ树定义及 其操作的形式化描述，接着介绍了本计算模型采用的３Ｄ结构ＤＮＡ分子———ｋａｒｍｓ分子结构，详细给出了一棵 ｍ阶Ｂ树的构造步骤，最后实现了其查找、插入和删除等操作。提出了ＤＮＡ分子计算的３Ｄ结构和分治策略，具 有一定的可扩展性和并行性，对ＤＮＡ计算的其他模型有参考价值。 关键词：ＤＮＡ计算；可扩展性；并行计算；分治策略；ＤＮＡ编码 中图分类号：ＴＰ３１１　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１２）０５１７７５０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１２．０５．０４６ ＤｅｓｉｇｎａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＢｔｒｅｅ ｄａｔａｓｔｒｕｃｔｕｒｅｉｎＤＮＡｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ １，２ ２ ＺＯＵＣｈａｏｊｕｎ ，ＺＨＵＹａｌｉ （１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８２，Ｃｈｉｎａ；２．Ｄｅｐｔ．ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＨｅｎｇｙａｎｇＮｏｒ ｍａｌＵｎｉｖｅｒｓｉｔｙ，ＨｅｎｇｙａｎｇＨｕｎａｎ４２１００２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＴｈｅｂｅｓｔｖｉｒｔｕｅｓｏｆＤＮＡｃｏｍｐｕｔｉｎｇａｒｅｔｈｅｍａｘｉｍｕｍｄｅｎｓｉｔｙｏｆｓｔｏｒａｇｅａｎｄｔｈｅｈｕｇｅｐａｒａｌｌｅｌｏｆｃｏｍｐｕｔｉｎｇｂｅｃａｕｓｅ ｏｆｔｈｅｆｅａｔｕｒｅｓｏｆＤＮＡｍｏｌｅｃｕｌｅｓ．ＩｔｉｓｉｍｐｏｒｔａｎｔｆｏｒａｎｙＤＮＡｃｏｍｐｕｔｉｎｇｍｏｄｅｌｔｏｃｈｏｏｓｅｓｏｍｅＤＮＡｍｏｌｅｃｕｌｅｓａｎｄｃｏｄｅ ｔｈｅｍ．ＴｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄｔｈｅｍｅｔｈｏｄｏｆｄｅｓｉｇｎｉｎｇＢｔｒｅｅｉｎＤＮＡｃｏｍｐｕｔｉｎｇ．Ｆｉｒｓｔｌｙ，ｆｏｒｍａｌｌｙｄｅｓｃｒｉｂｅｄｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆＢ ｔｒｅｅａｎｄｏｐｅｒａｔｉｏｎｓ．Ｔｈｅｎ，ｄｅｓｃｒｉｂｅｄｔｈｅ３ＤＤＮＡｍｏｌｅｃｕｌｅｓ，ｋａｒｍｓＤＮＡｍｏｌｅｃｕｌｅｓｉｎｄｅｔａｉｌ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｐｒｏｐｏｓｅｄｔｈｅａｐ ｐｒｏａｃｈｏｆｃｒｅａｔｉｎｇａＢｔｒｅｅｗｉｔｈｍｓｕｂｔｒｅｅｓ．Ｆｉｎａｌｌｙ，ｐｒｏｖｅｄｔｈｅｏｐｅｒａｔｉｏｎｓ，ｓｕｃｈａｓｓｅａｒｃｈｉｎｇ，ｉｎｓｅｒｔｉｎｇａｎｄｄｅｌｅｔｉｎｇ．ＤＮＡ ｍｏｌｅｃｕｌｅｓｗｉｔｈ３Ｄｓｔｒｕｃｔｕｒｅａｎｄｄｉｖｉｄｅａｎｄｃｏｎｑｕｅｒｓｔｒａｔｅｇｙｗｅｒｅｓｃａｌａｂｌｅａｎｄｐａｒａｌｌｅｌ，ａｎｄｃｏｕｌｄｂｅｕｓｅｄｉｎｏｔｈｅｒＤＮＡｃｏｍ ｐｕｔｉｎｇｍｏｄｅｌ． Ｋｅｙｗｏｒｄｓ：ＤＮＡｃｏｍｐｕｔｉｎｇ；ｓｃａｌａｂｉｌｉｔｙ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｄｉｖｉｄｅａｎｄｃｏｎｑｕｅｒｓｔｒａｔｅｇｙ；ＤＮＡｅｎｃｏｄｉｎｇ