EFFICIENT RECURSIVE LINKING ALGORITHM FOR COMPUTING THE LIKELIHOOD OF AN ORDER OF A LARGE NUMBER OF GENETIC MARKERS

S. Tewari, S. M. Bhandarkar*, J. Arnold

Dept. of Computer Science, University of Georgia, Athens, GA 30605-7404, USA. suchi@cs.uga.edu

Comput Syst Bioinformatics Conf. August, 2006. Vol. 5, p. 191-198. Full-Text PDF

*To whom correspondence should be addressed.

Assuming no interference, a multi-locus genetic likelihood is implemented based on a mathematical model of the recombination process in meiosis that accounts for events up to double crossovers in the genetic interval for any specified order of genetic markers. The mathematical model is realized with a straightforward algorithm that implements the likelihood computation process. The time complexity of the straightforward algorithm is exponential without bound in the number of genetic markers and implementation of the model for more than 7 genetic markers is not feasible, motivating the need for a novel algorithm. A recursive linking algorithm is proposed that decomposes the pool of genetic markers into segments and renders the model implementable for a large number of genetic markers. The recursive algorithm is shown to reduce the order of time complexity from exponential to linear. The improvement in time complexity is shown theoretically by a worst-case analysis of the algorithm and supported by run time results using data on linkage group-I of the fungal genome Neurospora crassa.