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

作　　者：Luyan Zhang Huihui Li Lei Meng Jiankang Wang 

机构地区：[1]National Key Facility for Crop Gene Resources and Genetic Improvement,Institute of Crop Sciences,Chinese Academy of Agricultural Sciences,Beijing 100081,China

出　　处：《The Crop Journal》2020年第5期701-712,共12页作物学报（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China(31861143003);HarvestPlus(part of the CGIAR Research Program on Agriculture for Nutrition and Health,http://www.harvestplus.org/).

摘　　要：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.

关 键 词：OPTIMAL algorithm TRAVELING 

分 类 号：S330[农业科学—作物遗传育种]