Design and analysis of an efficient recursive linking algorithm for constructing likelihood based genetic maps for a...

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Accurate genetic mapping relies on calculating multi-locus likelihoods based on recombination frequencies.
• Existing computational methods face limitations with increasing numbers of genetic markers due to high time complexity.

Purpose of the Study:

• To develop an efficient algorithm for computing multi-locus genetic map likelihoods.
• To overcome the computational challenges associated with ordering and spacing numerous genetic markers.

Main Methods:

• A novel recursive linking algorithm was developed to compute the likelihood of genetic map configurations.
• The algorithm utilizes an iterative Expectation-Maximization (EM) procedure for maximum likelihood estimation (MLE).
• Theoretical analysis and empirical testing on Neurospora crassa linkage group-II data were performed.

Main Results:

• The proposed recursive algorithm reduces computational time complexity from exponential to linear with respect to the number of markers.
• This advancement makes genetic map computation feasible for hundreds of markers, a significant improvement over previous limitations.
• Runtime analysis confirmed the theoretical efficiency gains.

Conclusions:

• The recursive linking algorithm provides a computationally efficient and scalable solution for multi-locus genetic mapping.
• This method enhances the ability to construct high-resolution genetic maps, aiding in genome analysis and gene discovery.
• The algorithm's efficiency is critical for handling large-scale genomic datasets.