A Multi-Fragment Heuristic Algorithm Of Marker Ordering In Building Genetic Linkage Maps

Construction of genetic linkage maps is the first essential stage in genetic studies, gene mapping, gene fine mapping and map-based cloning. Fast development and advances in molecular breeding has led to the high throughput molecular markers, which allow the construction of high density genetic maps. However, the large number of molecular markers also requires high efficient algorithms for linkage map construction. The construction of linkage maps can be viewed as the claasical traveling salesman problem (TSP), where distance between two cities is viewed as the recombination frequency between two markers. TSP is a classical NP (non-deterministic polynomial) hard problem in mathamatics. In theory, the optimum of a TSP can be found through the comparison of all possible solutions. But when the number of cities is large, the number of possible solutions tends to be infinite, requiring extensive computing time. Therefore, approximate and heuristic algorithms have been proposed in solving TSP. In this study, we propsed an multi-fragment heuristic (MF) algorithm based on matroid theory in ordering a large number of markers along a linkage map or chromosome. Simulations were conducted to compare the new methods with previous methods, by considering different marker number, marker densities, population types, and missing marker levels. Major results are sumarized as follows.1. The multi-fragment (MF) heuristic algorithm in ordering markers. Two approximate algorithms have been proposed in sovling TSP:tour construction algorithm and tour transformation algorithm. Tour construction algorithm is based on the theory embryos of greedy algorithm used in solution of TSP problem, constructing the initial path of a linkage map with the relationship of markers obtained by the known marker genotype information. MF is a complex algorithm of TSP construction algorithm and TSP transformation algorithm. It is based on the theory embryos of greedy algorithm used in solution of TSP problem, constructing the initial path of a linkage map with the relationship of markers obtained by the known marker genotype information. In order to make the linkage map closer to the global optimal solution but the local optimal solution, multi-fragment heuristic transformation algorithm use the form of 2-Opt or 3-Opt exchange of local search algorithm.2. Comparion of the multi-fragment heuristic algorithm with other algorithms. Using one actual maize and one rice linkage map,20 biparental populations were simulated by QTL IciMapping software (www.isbreeding.net). These populations were repreeneted by P1BC1F1,P2BC1F1,F1DH, F1RIL, P1BC1RIL, P2BC1RIL, F2, F3, P1BC2F1, P2BC2F1, P1BC2RIL, P2BC2RIL, P1BC1F2, P2BC1F2, P1BC2F2, P2BC2F2, P1BC1DH, P2BC1DH, P1BC2DH and P2BC2DH. Each type of population has a size of 200, and was repeated for 100 times. These populations represent commonly used genetic populations, and then used to comparing the efficiency of different ordering algorithms. MF algorithm was compared with four currently used algorithms SER (seriation), RCD (random chain delineartion) and RECORD (REcombination Counting and ORDering), and UG (unidirectional growth). Criteria for comparison were length of the linkage map, Euclidean distance of the linkage map, correlation, proportion of correctly ordering, and proportion of optimum solutions. Results indicated that MF algorithm had advantage over other algoritim for all criteria.3. Effect of missing and segregation distorted markers on linkage map. To investigate the effect of missing and segregation distorted markers on linkage map, 200 RIL and 200 F2 populations with three levels of missing (i.e.0,10%, and 20%), and three levels of selection (i.e.1:1:1,1:0.6:0.2, and 1:0.4:0 for fitness of the three genotypes) were simulated using the breeding simulation tool QuLine. Each population has a size of 200. Results indiataed that missing markers reduce the accuracy of the linkage map, while the segregation distorted markers have little effects on the accuracy of the linkage map.4. The MF algorithm for over-saturated markers. We simulated different numbers of markers on one linkage map, i.e.200,500,1000,1500, and 2000 to see the performance of MF for an increased number of markers, assuming markers were evenly distributed. Constructed map from different algorithm showed that MF algorithm is better than other four methods, especially for high-density markers, for several evaluation criteria of genetic distance and position. In addition, MF required less CPU time, indicating that MF is also suitable for building linkage maps of over-saturated markers.