Ordering of high-density markers by the k-Optimal algorithm for the traveling-salesman problem
2020
Zhang, Luyan | Li, Huihui | Meng, Lei | Wang, Jiankang
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.
显示更多 [+] 显示较少 [-]