基因组重构是改变基因在基因组中排列顺序的生物过程，可归结为三种主要操作：移位、反转和转位。重组距离即从一个基因组转化为另一个基因组所需的最少重组次数。双重基因组中每条染色体都是成对出现的。双重基因组重构问题，即要求计算一个与给定基因组移位距离最短的双重基因组。对于该问题，Nadia E1—Mabrouk等人给出了一个多项式时间算法。本文利用Delphi集成开发环境，将该算法实现为双重基因组重构软件，设计了优化的数据结构，给出了详细的实现方法，调试验证了算法的正确性。文章介绍了双重基因组重构算法的研究背景，针对双重基因组重构算法的基本思想，详细介绍了算法所涉及的基本概念与理论知识。然后通过一个基因组实例，详细介绍了算法实现的数据结构。最后重点介绍了双重基因组重构软件的设计，并对软件进行了分析。运行双重基因组重构软件，用户输入一个初始基因组，经过该软件自动处理，即可输出一个目标基因组（即双重基因组）。主要处理步骤如下： ⑴由初始基因组生成自然子图。初始基因组是一个重排后的双重基因组，由偶数条染色体组成，每个基因出现两次。初始基因组用断点图来进行描述，每个基因符号在断点图中用两个顶点来表示，两个相邻基因的顶点用一条黑色的边来连接。每条染色体的两端分别引进了一个特殊的顶点，用符号O来表示，简称O点。在算法的实现中，初始基因组的断点图用链表结构来描述，每条黑边对应链表中的一个结点，同一染色体中的结点通过指针从左到右的顺序进行连接，多条染色体构成的链表，通过一个指针数组连接成一个链表结构。输入初始基因组中的符号，程序自动生成初始基因组的链表结构，再对该链表结构进行处理，生成自然子图对应的链表结构。 ⑵将自然子图合并为超自然子图。自然子图根据所含边数的奇偶性可以分为两类，由偶数条边组成的自然子图和由奇数条边组成的自然子图。由偶数条边组成的自然子图只需按照黑边从上到下的顺序配对排序，即可生成对应的超自然子图。由奇数条边组成的自然子图又可分为两个小类，包含O点的自然子图和不包含O点的自然子图，上述两小类中的自然子图要分别进行两两合并与配对排序，生成边数为偶数的超自然子图。如果每个小类中还剩余一个自然子图，则要将这两个自然子图进行合并与配对排序，从而得到一个对应的超自然子图。每个超自然子图对应了一个链表，多个超自然子图的链表通过一个指针数组连接成一个动态的链表结构。 ⑶处理超自然子图生成目标基因组。对每个超自然子图对应的链表依次进行处理，每次生成一对灰色的边（一条灰边对应一个结点）。随着灰边的不断生成，灰边与灰边之间的相互邻接，最后得到目标基因组的链表结构。根据链表结构进行处理，即可得到一个目标基因组。目标基因组是一个完美双重基因组，即基因组中的染色体是两两相同的。在算法的实现过程中，初始基因组、自然子图、超自然子图、目标基因组都采用动态链表结构来描述，从而提高了程序的灵活性与处理效率。在软件的具体实现中，由于每个基因只能出现两次，所以在输入基因符号后，程序增加了对基因符号的正确性检验。通过反复运行调试程序，证明了双重基因组重构算法的正确性。