Statistics and Its Interface

Volume 4 (2011)

Number 3

Stochastic deletion-insertion algorithm to construct dense linkage maps

Pages: 381 – 387



Michael Gonda (Animal and Range Science Department, South Dakota State University, Brookings, S.D., U.S.A.)

Xiang-Yang Lou (Section on Statistical Genetics, Department of Biostatistics, University of Alabama at Birmingham, U.S.A.)

Jixiang Wu (Plant Science Department, South Dakota State University, Brookings, S.D., U.S.A.)


In this study, we proposed a stochastic deletion-insertion (SDI) algorithm for constructing large-scale linkage maps. This SDI algorithm was compared with three published approximation approaches, the seriation (SER), neighbor mapping (NM), and unidirectional growth (UG) approaches, on the basis of simulated $F_2$ data with different population sizes, missing genotype rates, and numbers of markers. Simulation results showed that the SDI method had a similar or higher percentage of correct linkage orders than the other three methods. This SDI algorithm was also applied to a real dataset and compared with the other three methods. The total linkage map distance (cM) obtained by the SDI method (148.08 cM) was smaller than the distance obtained by SER (225.52 cM) and two published distances (150.11 cM and 150.38 cM). Since this SDI algorithm is stochastic, a more accurate linkage order can be quickly obtained by repeating this algorithm. Thus, this SDI method, which combines the advantages of accuracy and speed, is an important addition to the current linkage mapping toolkit for constructing improved linkage maps.


linkage mapping, stochastic deletion-insertion algorithm

2010 Mathematics Subject Classification

Primary 60H30. Secondary 60E15.

Published 29 August 2011