生物序列拼装欧拉路径算法的Gamma描述及其并行化研究  

Specification and Parallelization of Eulerian-path Algorithm of Sequence Assembly Using Gamma Model

作　　者：廖文昭[1] 童维勤[1] 蔡立志[1] 

机构地区：[1]上海大学计算机学院,上海200072

出　　处：《小型微型计算机系统》2004年第4期707-711,共5页Journal of Chinese Computer Systems

摘　　要：序列拼装是生物基因测序的一个重要环节 ,也是生物信息学重要的研究内容 .〔2〕中将 Eulerian路径的方法应用于序列拼接 ,较好地解决传统序列拼装软件中存在的 repeat问题 ,从而提高序列拼装的精度 .但对于该方法的研究目前还只有串行化的实现 ,拼装速度不够理想 .在本文中 ,我们采用了并行化 Gamma模型形式化地描述了用于序列拼装的 Eulerian方法 ,并给出了Sequences assembly plays a vital role in bioinformatics research. The Eulerian path approach reduces the sequence assembly to a variation of the classical Eulerian path problem that solves the 'repeat' problem existing in the traditional sequence assembly program .It allows one to generate accurate solutions of sequencing problems. As the approach only has sequential implementation , we use a parallel Gamma model to formalize the Eulerian path algorithm of sequence assembly . Finally we present a scheme of parallel implementation of the Gamma program.

关 键 词：序列拼装 Gamma模型 并行化 欧拉路径 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]