生物的遗传物质随着进化而改变,相对于单个基因或少数几个基因组成的基因块的点变化,越来越多的研究更加关注基因组水平的较大变化。基因组重排是生物分子进化的一种重要模式,是计算分子生物学研究的一个重要问题,特别是基于反转的基因组重排的数学特征及算法的研究,一直受到广泛关注。由此产生了借助于反转来排序无向排列的问题,即给定可以代表基因组的两个排列,找到由一个排列转化到另一个排列的最优方案。遗传算法是一种基于自然选择和基因遗传学原理的全局性概率搜索算法,它已经过了三十多年的研究与实践。免疫学已成为一门学科,引起了国内外学者的注意。对于并行计算,这是一个充满活力的领域,它经过几十年的发展,这一领域的研究成果已在科学与技术的众多领域中随处可见。本文提出的是一种基于并行免疫遗传算法的无向排列的反转排序的方法,将一种免疫算子加入到遗传算法的框架中,通过对个体接种疫苗来进一步提升个体的存活能力,免疫遗传算法作为集免疫机制和进化机制于一体的全新演化算法应用到反转基因组重排的问题上是一种新的尝试,可以避免遗传算法存在的早熟缺点,同时使免疫遗传算法并行化可以提高收敛速度,由于无向排列的基因组反转排序问题是NP难题,现有的算法都是近似算法,因此将提高近似解的精确度。