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

序列拼装是生物基因测序的一个重要环节,也是生物信息学重要的研究内容．2]中将Eulerian路径的方法应用于序列拼接,较好地解决传统序列拼装软件中存在的repeat问题,从而提高序列拼装的精度,但对于该方法的研究目前还只有串行化的实现,拼装速度不够理想．在本文中,我们采用了并行化Gamma模型形式化地描述了用于序列拼装的Eulerian方法,并给出了Gamma程序的并行化实现方案．

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

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.