A Study On Ordering Molecular Marker Loci In A Genetic Linkage Group

Constructing genetic linkage maps is very important in genetic breeding, which include two-point linkage analysis, multiple locus linkage analysis, linkage grouping, and multiple locus ordering. The key step for accurately constructing genetic linkage maps is multiple locus ordering. For several marker loci in a linkage group, exhaust method can be applied for searching the optimal order. However, for more than a dozen of markers, it is unfeasible to find the best order through exhaust search algorithm because the number of all possible orders is so huge. Multiple locus ordering is known as a NP problem or traveling salesman problem(TSP). Although a number of algorithms are available, many either are low in the accuracy of recovering the true order of locus or require tremendous amounts of computational resources. Through computer simulations, this paper demonstrated that the likelihood value of a given order of markers based on HMM is effective as an objective function in multiple locus ordering. In the mean time, the computing time for ordering marker loci was summarized under different environment. For ordering large number of markers, we proposed the simulated annealing parallel algorithm and the heuristic searching parallel algorithm, and implemented with C+MPI. We found that the two parallel algorithms are more powerful than the famous linkage mapping software, Mapmaker, in ordering accuracy and computing time by performing Monte Carlo simulations in F2 population. The result provides a solution for constructing high-density genetic linkage maps in forest trees.