Ordering of high-density markers by the k-Optimal algorithm for the traveling-salesman problem

文献类型： 外文期刊

第一作者： Zhang, Luyan

作者： Zhang, Luyan;Li, Huihui;Meng, Lei;Wang, Jiankang

作者机构：

期刊名称：CROP JOURNAL （ 影响因子：4.407； 五年影响因子：5.687 ）

ISSN： 2095-5421

年卷期： 2020 年 8 卷 5 期

页码：

收录情况： SCI

摘要： Construction of accurate and high-density linkage maps is a key research area of genetics. We investigated the efficiency of genetic map construction (MAP) using modifications of the k-Optimal (k-Opt) algorithm for solving the traveling-salesman problem (TSP). For TSP, different initial routes resulted in different optimal solutions. The most optimal solution could be found only by use of as many initial routes as possible. But for MAP, a large number of initial routes resulted in one optimal order. k-Opt using open route length gave a slightly higher proportion of correct orders than the method of adding one virtual marker and using closed route length. Recombination frequency (REC) and logarithm of odds (LOD) score gave similar proportions of correct order, higher than that given by genetic distance. Both missing markers and genotyping error reduced ordering accuracy, but the best order was still achieved with high probability by comparison of the optimal orders from multiple initial routes. Computation time increased rapidly with marker number, and 2-Opt took much less time than 3-Opt. The 2-Opt algorithm was compared with ordering methods used in two other software packages. The best method was 2-Opt using open route length as the criterion to identify the optimal order and using REC or LOD as the measure of distance between markers. We describe a unified software interface for using k-Opt in high-density linkage map construction for a wide range of genetic populations. (C) 2020 Crop Science Society of China and Institute of Crop Science, CAAS. Publishing services by Elsevier B.V. on behalf of KeAi Communications Co. Ltd.

分类号：

  • 相关文献
作者其他论文 更多>>

微信小程序