本科毕业论文-最长公共子序列问题的并行化研究

本科毕业论文-最长公共子序列问题的并行化研究 中国科学技术大学本科毕业论文 中国科学技术大学 本科毕业论文 题 目 最长公共子序列问题的并行化研究 英 文 Research on the Parallelization of 题 目 the Longest Common Subsequence Problem 院 系 计算机科学与技术 姓 名 易子越 学 号 PB07210190 导 师 徐云 日 期 二零一一年六月 中国科学技术大学本科毕业论文 致谢 4年大学生活一晃而过，回忆这4年所经历的各种事情，我心中感慨良多，在我写完这篇毕业论文的时候，我的内心产生了一种如释重负的感觉。 首先，我要诚挚地向我的毕业 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 指导教师徐云老师 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示感谢。他在忙碌的教学工作中挤出时间来指导我做毕业设计，并对我的论文加以审查。徐老师严谨细致、一丝不苟的作风是我今后学习的榜样。 其次，我要感谢我的班主任周宇老师及所有的任课教师和助教。他们对我在学习和生活上的悉心关怀与照顾，使得我这四年获得了许多学科方面相关的知识，也使我明白了许多为人处世的道理，让我对社会、对生活有了更深层次的了解。 再次，感谢实验室的师兄师姐们特别是杨矫云、聂鹏宇、腾达三位师兄，他们在我做毕业设计期间给予了我许多帮助，让我在做毕设的路上少走了许多弯路。我的朋友陆李、刘建波、谢天、江章伟、张文强等也在我平时的学习生活以及做毕业设计的过程中给了我很大的帮助，感谢你们。还有0711的同学们，正因为有你们，我才能在这样一个优秀的班集体中渡过这四年，十分感谢。 最后，我要感谢我的父母，感谢你们从小到大对我无微不至的关心、照顾以及支持。你们的恩情我无以为报，唯有刻苦努力，不辜负你们的期望。 谨在此再一次衷心地感谢我的父母、老师、学长、朋友、同学们，谢谢你们～ 中国科学技术大学本科毕业论文 目录 中文内容摘要 ........................................................................................................... 3 Abstract ..................................................................................................................... 4 第一章 引言............................................................................................................. 5 第一节 背景 ...................................................................................................... 5 一、生物学意义 ......................................................................................... 5 二、计算机科学意义 .................................................................................. 5 第二节 研究内容及工作思路 ........................................................................... 6 第三节 论文结构 .............................................................................................. 6 第二章 LCS研究现状 ............................................................................................. 7 第一节 概述 ...................................................................................................... 7 一、问题模型 ............................................................................................. 7 二、精确解算法 ......................................................................................... 7 三、并行算法 ............................................................................................. 8第二节 动态规划法 .......................................................................................... 9 一、算法简介 ............................................................................................. 9 二、时空复杂度分析 ................................................................................ 10 三、优化 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ........................................................................................... 10 第三节 基于支配点思想的方法 ...................................................................... 11 一、基本概念 ............................................................................................ 11 二、算法简介 ........................................................................................... 13 三、时空复杂度分析 ................................................................................ 14 第三节 本章小结 ............................................................................................ 14 第三章 基于分布式存储结构的并行支配点算法 ................................................. 15 第一节 实验平台 ............................................................................................ 15 一、硬件平台 ........................................................................................... 15 二、软件平台 ........................................................................................... 15 三、程序设计语言 ................................................................................... 15 第二节 算法流程 ............................................................................................ 15 一、数据结构 ........................................................................................... 15 二、初始化 ............................................................................................... 16 三、任务分配 ........................................................................................... 17 四、支配点的求取 ................................................................................... 17 五、结果汇总 ........................................................................................... 17 六、LCS的求取 ....................................................................................... 18 第三节 实验结果与优化想法 ......................................................................... 18 一、实验结果 ........................................................................................... 18 二、优化想法 ........................................................................................... 23 第四节 本章小结 ............................................................................................ 23 1 中国科学技术大学本科毕业论文 第四章 总结........................................................................................................... 24 参考文献 ................................................................................................................ 25 2 中国科学技术大学本科毕业论文 中文内容摘要 最长公共子序列问题是一个经典的计算机科学问题，在生物信息学、分子生 数学、数据挖掘、模式识别、文本检索以及气体色谱分析等领域有重要应物学、 用。最长公共子序列问题可分为双序列最长公共子序列问题和多序列最长公共子序列问题，简称为LCS和MLCS。LCS(MLCS)问题是生物信息学的一个研究重点。由于新一代基因测序技术每周能产生400~500G左右的基因信息，这种急剧增长的信息需要更高性能的算法。LCS(MLCS)问题的经典解决方法为动态规划法，但是其对于双序列LCS(MLCS)问题的时间和空间消耗与序列长度呈二次增长，性能不够理想，尽管后人做了大量研究和改进，依然不能使原有算法的性能得到大幅提高。将串行算法并行化可以有效利用计算机资源并在相同问题规模的前提下大幅减少时间消耗，然而经典的动态规划法直接并行化难度较大。基于支配点思想的算法是近年来提出的最好的一种解决LCS(MLCS)问题的算法，其算法为逐层扩展独立求解，适用于并行化。 本文通过对已有算法的研究和分析，提出一种针对MLCS问题的以支配点思想为核心的基于分布式存储结构的并行算法，并在KD-50-I上予以实现。 关键字:最长公共子序列 支配点 并行 KD-50-I 3 中国科学技术大学本科毕业论文 Abstract The longest common subsequence problem is a classic problem in computer science. It is widely applied on bioinformatics, molecular biology, mathematics, data mining, pattern recognition, text retrieval and gas chromatographic analysis. The longest common subsequence problem can be divided into the longest common subsequence problem for two and the multiple longest subsequence problem, LCS and MLCS for short. The LCS(MLCS) problem is one of the important problems in bioinformatics . As with a new generation of gene sequencing technology , the genetic information increases 400 ~ 500G per week. This rapid growth of information needs a more high-performance algorithms. Classic solution to the LCS(MLCS) problem is the dynamic programming. But even to the LCS(MLCS) problem of two, the time and space consumption grows quadratically with the length of the sequences. That is last thing we want to see. Although a lot of research is been done and some improvements is really made as a result, the original algorithm can not achieve a dramatic improvement. Parallelizing the sequential algorithm can make an efficient use of existed computer resources. In the premise of the same scale, we can get a substantial reduction in time consuming. However, the classic dynamic programming is difficult to parallelize. Algorithm based on the dominant points theory performs the best in recent years. The algorithm runs independently layer by layer, thus ,it is easy for parallelization. In this thesis, we talk about the existing researches and analysis those algorithms, then represent a parallel algorithm to the MLCS problem based on dominant points applied on distributed memory structure, and realize it on the KD-50-I. Keywords: Longest common subsequence Dominant points Parallelization KD-50-I 4 中国科学技术大学本科毕业论文 第一章 引言 第一节 背景 一、生物学意义 随着基因工程相关技术的飞速发展，新的分子生物信息数据大量涌现。因此在生物信息学研究中，最首要的任务是如何从海量的数据提取出有价值的知识。而“比较”是我们最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。DNA片断比对是最常用最经典的手段，即将未知序列同已知序列进行比较分析为序列或字符串的最长公共子序列问题。因为人体DNA 链中的碱基只有4种:腺嘌呤(A)、胸腺嘧啶(T)、鸟嘌呤(G)和胞嘧啶(C)。从而该问题实质上就是一个基于字符表? = {A，C，G，T }的LCS问题。在现今基因测序等技术分飞速发展下，DNA 和蛋白质序列数据库的规模正呈指数增加。伴随着序列数据库的增长，三维结构数据库也在不断增长，于是，在精确度不受影响的前提下, 如何提高序列比对的速度和效率成了一项重要的课题。序列比对的目的是求出给定的序列对之间的距离，从而为诸如DNA分类、聚类、蛋白质的二级结构预测和生物进化树的创建打下基础，提供了一个相似性度量的基本工具。人们对于序列比对中的最长公共子序列问题，已经作了大量的研究工作。已有人证明了对于双序列的最长公共子序列问题的串行算法的时间复杂度的下界为O (m n) (m和n分别为两条序列的长度)，使用动态规划法可以达到时间和空间的复杂度为O (m n)。研究表明若对该问题采用并行化的算法可以加快问题求解速度。 二、计算机科学意义 最初对LCS问题的研究是将它作为一种差分压缩算法来研究的。例如，在版本管理系统中，一个文件经过不断地修改产生 不同的版本，新产生的版本相对老版本变化并不大。为了节省存储空间，我们可以将老文件版本与修改后新版本进行比较，找出它们的相同部分和不同部分。这样就不必将原始文件和修改文件都独立存储，而只需存储老文件版本以及新老版本的不同部分即可。这种增量式存储方法在文件版本较多的情况下能够大大提高存储效率。两个文件版本的比 5 中国科学技术大学本科毕业论文 较就类似于LCS问题。 又例如其再程序代码相似度度量的应用。一种程序语言，对于同一逻辑的表达形式往往是多样的。还有可能一些人为了节省时间和力气，将别人的程序采用编辑手段，作一些文本的改变( 简单的改变如改变代码注释或改变变量名，稍复 ) ) 。可以杂一些如等价控制结构的替换( 如用“while”循环替换“for ”循环肯定的说，这些更改都是表面的，是少量的，而程序中内含的属性和结构是没有改变的。在高等院校的程序设计课程中，程序复制的现象屡见不鲜，将程序代码相似度应用在程序的复制 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 中，可以起到督促学生学习、增加学生学习兴趣、培养良好的学风的作用。另外将其应用在知识产权保护中，无论对个人或企业都具有极其重要的意义和价值。 第二节 研究内容及工作思路 本文将介绍已有的LCS问题算法，并着重分析几种精确解算法，之后将其中一种算法改造为基于分布式存储结构的并行算法并在KD-50-I上予以实现，之后提出一些可能的优化方案。 第三节 论文结构 本文第一章介绍最长公共子序列子序列问题在生物学以及计算机科学上的背景及应用，并且阐述了研究内容及基本工作思路。 第二章先给出最长公共子序列问题的问题模型，之后介绍其研究现状以及并行计算相关知识，并详细地对其中的几种重要算法进行说明和分析。 第三章给出了一个具体的基于分布式存储结构的并行算法，且在KD-50-I上加以实现，对所得出的结果进行分析，并提出几种优化方案。 第四章总结了前文的工作。 6 中国科学技术大学本科毕业论文 第二章 LCS研究现状 第一节 概述 一、问题模型 1.基础概念 以Σ表示项目表，这里DNA序列为例，则Σ={A，T，C，G}。这里需要注意的是项目可以不仅仅是单一的字符。 x,x,…,x是定义在字母表Σ上的长度为n,n,…,n的项目串，令x=ss…s12k12ki12n，对于任意的1<=j<=n均有s?Σ。 iij 令a=sss，如果对于任意的j，1<=j<=l，均有1<=i<=n，且对于所有的i1i2…iljks、t，1<=s 计算公式 六西格玛计算公式下载结构力学静力计算公式下载重复性计算公式下载六西格玛计算公式下载年假计算公式 为: 当矩阵L建立完成后，我们就可以通过从点[n n]回溯到点[0,0]的办法由L1,2 中提取出一条LCS(MLCS)。令|LCS|(|MLCS|)为LCS(MLCS)的长度，我们可以证明|LCS|(|MLCS|)是矩阵L中的最大值。这里我们令a=GATTACA，1a=GTAATCTAAC，所得矩阵如图2-2-1: 2 9 中国科学技术大学本科毕业论文 图2-2-1 以序列GATTACA和序列GTAATCTAAC为输入计算得到的矩阵L 图中用红色的边框分隔出7组具有相同值的点集，处于每个区域拐角处的被圆圈所圈住的点为支配点，在下一节会做详细介绍。由此矩阵即可从右下角开始回溯计算得长度为6的LCS，其中一条为GATTAC。 二、时空复杂度分析 由于动态规划法的所有的计算都在于L中，其对于d条长度为n序列的时 d空复杂度为O(n)。 三、优化方案 1.缩减问题集 矩阵L的规模随着序列长度的增长而呈二次增长。对于两个长度为100的序列，矩阵大小将为10,000，即需要做10000次比较。在有些现实世界中的情况下，特别是比较和修补程序的源代码，文件的开头和结尾很少改变，并且几乎肯定不是一同发生。如果是只有几个项目在变化的序列中，开始和结束的部分是可以消除的。这样，缩小了的矩阵不仅降低了对存储器的要求，而且减少了比较次数。 在最理想的情况下，即两个序列完全相同，将不需要建立矩阵L。考虑在最坏的情况下，也仅仅只比原先的算法多两次比较。 10 中国科学技术大学本科毕业论文 2.减少比对时间 由于原算法所需的时间大部分都花在序列之间的项目的比较，对于源代码文本序列，我们需要比对的项目的不是单个字符，而是一行字符。这意味着算法中对每个相对较长的字符串比较的时间可以大幅减少。这两个优化可以帮助减少这些比较消耗的时间。 3.用哈希(hash)减少比较字符 一个哈希函数或校验和可以用来减少序列中的字符串的长度。也就是说，对于源代码，其中平均每一行是60个或更多个字符，哈希或该行的校验可能只有8至40个字符。此外，随机的哈希和校验的性质将保证比较将能够进行得更快，因为源代码的每一行很少会在开始的部分改变。 这种优化有三个主要的缺点。首先，需要花费时间事前预先计算两个序列的哈希。其次，需要更多的内存为新的哈希序列分配。然而，对于原先的算法而言，这些缺点都是相对较小的。 第三个缺点是可能会发生碰撞 。由于校验或哈希不能保证是独一无二的，有一种很小的可能，就是两个不同的项目可能会计算得到相同的哈希。这虽然是在源代码不太可能，但它确实是可能的。 4.减少所需空间 如果仅仅只需要知道LCS的长度，则矩阵的规模可以减少到2*min(n,m)(n、m分别为两条序列的长度)，或min(n,m)+ 1的向量，这是由于动态规划法只需要知道矩阵中现在的值及其前驱。 第三节 基于支配点思想的方法 一、基本概念 如果对于一个点p[p,p…p] 有a[p]=a[p]=„=a[p]，则我们把这样一个12d1122dd 点称为一个匹配，例如图1-1-1中的[0,0]和[1,2]，他们对应的字母表上的字符分别为G、A。 如果对于两个点p[p,p,...,p]及q[q,q,…,q]有p<=q(对于所有0<=i<=d)，12d12dii 我们称p支配q，写作p<=q。若对于所有i均有p=q(p>q)，则p不支配(严格iiii 支配)q，可能存在的情况是p和q均不能支配或是严格支配对方。 11 中国科学技术大学本科毕业论文 对于项目表Σ中的任意字符s，点p的s-parent点q定义如下: 1.q为匹配了s的点，即q为一个匹配，且各序列在该位置处的字符为s。 2.p0 do{ 13 中国科学技术大学本科毕业论文 11 current LCS position=a[p]; 11 12 pick a point q such that p?Par(q,?); 13 p=q; 14 k=k-1;} 由该伪代码我们可以可以看出该算法包含2个部分。在第一部分，我们从第0层开始迭代地计算出了所有的支配点集。在第二部分，我们根据由第一部分计算出来的各层支配点集，从最后一层的一个点开始回溯得到一条MLCS。如果有必要的话，我们可以得到所有的MLCS。 kk本算法遵循以下两个步骤计算Par(D,?)的最小集:1.对于每一个点q?D， k计算Minima(Par(D,?))，然后将这些点集合并;2.计算无重叠的点集Minima(P kk+1ar)，s??。有定理表明上文提到的两个步骤能够正确地由D计算得到D。 s 三、时空复杂度分析 由[3]，对于d条长度为n的序列，其支配点数为D，其时间复杂度为O(n| d-2d-2?|d+|D||?|d(logn+log|?|))，空间复杂度为O(|D|d+n|?|d)。 第三节 本章小结 本章先给出了LCS问题的问题模型，而后介绍了现在关于LCS问题的研究状况以及并行算法和相关知识，并详细介绍了两种能够得到精确解的方法:动态规划法及基于支配点思想的算法。动态规划法是一种已有的经典的常用于双序列LCS问题的算法，但是其难以并行且在多序列LCS问题上性能不佳。基于支配点思想的算法是近年来提出的一种高效的算法，其分层求解，符合并行化要求，易于并行化。 14 中国科学技术大学本科毕业论文 第三章 基于分布式存储结构的并行支配点算法 第一节 实验平台 一、硬件平台 基于龙芯2号国产万亿次高性能计算机KD-50-I。 二、软件平台 Debian/GNU Linux无盘系统，支持C/C++和Fortran77/90/95程序及MPI并行，利用TORQUE和Maui进行资源管理和作业调度。 三、程序设计语言 C语言、MPI。 第二节 算法流程 一、数据结构 以DNA序列为例，项目表为{A、T、G、C}。每一条序列占用一个一维字符型数组，令为seq[i]。 考虑所发送的消息的连续性，采用一维整型数组作为点集的存储结构，每一层点集令为D_1_K[i]，0<=i<=length(length为序列长度，下同。这里假定所有序列长度相同，事实上，我们可以把所有序列用指定的特殊字符补至最长序列长度)。假定D_1_K[i]为n，则对于0<=j