DNA测序是分子生物学进一步研究的基础，但测序是一项艰巨的工作，因为直接使用显微镜读取DNA序列是不可行的，而间接的测序方法即使非常严密也避免不了错误的产生。DNA杂交测序(Sequencing by Hybridization，SBH)是目前使用最多的测序方法，该方法分为杂交实验和序列重构两个步骤。其中杂交实验产生的错误使得序列的重构更加困难，已经证明含有错误的序列重构问题是NP-hard问题。在实际研究当中，生物学工作者面对的是含有数万个碱基的DNA序列，因此，如何使得重构的序列更加精确，耗费时间更少，是本课题的目的与意义所在。　　 国内外现有的求解DNA杂交测序问题的算法大致分为两类：精确算法和启发式搜索方法。精确算法有分支定界算法，动态规划方法等；启发式搜索方法有禁忌搜索算法，遗传算法，蚁群算法，模拟退火算法等。比较之下，启发式搜索方法得到的解更优，但随着数据规模的增大，算法的性能随之下降。因此，进一步的研究工作是提高解的精度和收敛速度。　　 蚁群算法是在蚂蚁群体觅食过程中沿最短路径行进的生物学行为之上发展起来的一类群集智能优化方法，吸引了众多学者的注意。经过近20年的研究与实践，蚁群算法已显示出它在求解复杂优化问题的优势。它具有强大的全局寻优能力，较强的鲁棒性和适应性，且易于与其他算法融合，除此之外，蚁群算法固有的并行性非常适用于大规模并行计算，因此它已在组合优化和并行处理等领域得到了越来越广泛的应用。　　 首先，本文对并行计算、蚁群算法和并行蚁群算法的发展和特点进行综述，并介绍并行处理的硬件系统及支撑软件，其中主要叙述PC机群及该平台上采用的编程环境MPI(Message Passing Interface)。其次，将DNA序列重构问题与图论相结合，转化为一种特殊的哈密尔顿路径问题，并作形式化描述。再次，对最大最小蚁群算法做两方面改进，一是分别采用了双向构造解路径，二是利用不同阶段的最优解更新信息素；同时根据主从式并行程序的设计思想提出了一种新的信息交换策略——排序交叉信息交换策略。最后，搭建机群，详细描述其步骤，使用C语言编写程序并调试运行。　　 实验结果表明，在求解DNA杂交测序问题上，本文提出的并行蚁群算法提高了解精度和收敛速度，在求解规模较大的数据集时仍表现出良好的搜索能力，这优于现有的串行蚁群算法，禁忌搜索算法和进化算法。此外，并行蚁群算法的应用研究将有助于其他组合优化问题的解决。