Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem
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 resul...
| Autores principales: | , , , |
|---|---|
| Formato: | Journal Article |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier
2020
|
| Materias: | |
| Acceso en línea: | https://hdl.handle.net/10568/171258 |
| _version_ | 1855539479371055104 |
|---|---|
| author | Zhang, Luyan Li, Huihui Meng, Lei Wang, Jiankang |
| author_browse | Li, Huihui Meng, Lei Wang, Jiankang Zhang, Luyan |
| author_facet | Zhang, Luyan Li, Huihui Meng, Lei Wang, Jiankang |
| author_sort | Zhang, Luyan |
| collection | Repository of Agricultural Research Outputs (CGSpace) |
| description | 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. |
| format | Journal Article |
| id | CGSpace171258 |
| institution | CGIAR Consortium |
| language | Inglés |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| publisher | Elsevier |
| publisherStr | Elsevier |
| record_format | dspace |
| spelling | CGSpace1712582025-01-29T12:57:55Z Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem Zhang, Luyan Li, Huihui Meng, Lei Wang, Jiankang genetic maps genetic markers algorithms 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. 2020-10 2025-01-29T12:57:55Z 2025-01-29T12:57:55Z Journal Article https://hdl.handle.net/10568/171258 en Open Access Elsevier Zhang, Luyan; Li, Huihui; Meng, Lei; and Wang, Jiankang. 2020. Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem. Crop Journal 8(5): 701-712. https://doi.org/10.1016/j.cj.2020.03.005 |
| spellingShingle | genetic maps genetic markers algorithms Zhang, Luyan Li, Huihui Meng, Lei Wang, Jiankang Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title | Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title_full | Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title_fullStr | Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title_full_unstemmed | Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title_short | Ordering of high-density markers by the k-optimal algorithm for the traveling-salesman problem |
| title_sort | ordering of high density markers by the k optimal algorithm for the traveling salesman problem |
| topic | genetic maps genetic markers algorithms |
| url | https://hdl.handle.net/10568/171258 |
| work_keys_str_mv | AT zhangluyan orderingofhighdensitymarkersbythekoptimalalgorithmforthetravelingsalesmanproblem AT lihuihui orderingofhighdensitymarkersbythekoptimalalgorithmforthetravelingsalesmanproblem AT menglei orderingofhighdensitymarkersbythekoptimalalgorithmforthetravelingsalesmanproblem AT wangjiankang orderingofhighdensitymarkersbythekoptimalalgorithmforthetravelingsalesmanproblem |