Mester D I, Ronin Y I, Nevo E, Korol A B
Institute of Evolution, University of Haifa, Haifa 31905, Israel.
Comput Biol Chem. 2004 Oct;28(4):281-90. doi: 10.1016/j.compbiolchem.2004.08.003.
There are several very difficult problems related to genetic or genomic analysis that belong to the field of discrete optimization in a set of all possible orders. With n elements (points, markers, clones, sequences, etc.), the number of all possible orders is n!/2 and only one of these is considered to be the true order. A classical formulation of a similar mathematical problem is the well-known traveling salesperson problem model (TSP). Genetic analogues of this problem include: ordering in multilocus genetic mapping, evolutionary tree reconstruction, building physical maps (contig assembling for overlapping clones and radiation hybrid mapping), and others. A novel, fast and reliable hybrid algorithm based on evolution strategy and guided local search discrete optimization was developed for TSP formulation of the multilocus mapping problems. High performance and high precision of the employed algorithm named guided evolution strategy (GES) allows verification of the obtained multilocus orders based on different computing-intensive approaches (e.g., bootstrap or jackknife) for detection and removing unreliable marker loci, hence, stabilizing the resulting paths. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on simulated data of multilocus genetic maps up to 1000 points per linkage group.
有几个与遗传或基因组分析相关的非常困难的问题，它们属于所有可能顺序集合中的离散优化领域。对于n个元素（点、标记、克隆、序列等），所有可能顺序的数量是n!/2，而其中只有一个被认为是真实顺序。一个类似数学问题的经典表述是著名的旅行商问题模型（TSP）。这个问题的遗传类似问题包括：多位点遗传图谱排序、进化树重建、构建物理图谱（重叠克隆的重叠群组装和辐射杂种图谱）等。针对多位点映射问题的TSP表述，开发了一种基于进化策略和引导局部搜索离散优化的新颖、快速且可靠的混合算法。所采用的名为引导进化策略（GES）的算法具有高性能和高精度，允许基于不同的计算密集型方法（例如，自助法或刀切法）验证获得的多位点顺序，以检测和去除不可靠的标记位点，从而稳定所得路径。该算法的效率在标准TSP问题以及每个连锁群多达1000个点的多位点遗传图谱模拟数据上得到了证明。
