Faster sequential genetic linkage computations

Area of Science:

• Genetics
• Bioinformatics
• Computational Biology

Background:

• Genetic linkage analysis, employing maximum-likelihood estimation, is crucial for gene mapping.
• Exponential growth in data size has led to significant computational impediments in linkage analysis.
• Previous research indicated parallel computation can accelerate linkage analysis.

Purpose of the Study:

• To demonstrate that algorithmic modifications can achieve order-of-magnitude speed improvements in genetic linkage analysis.
• To present implemented algorithmic enhancements within the LINKAGE software package.
• To showcase the application and efficacy of these computational techniques.

Main Methods:

• Implemented algorithmic improvements focused on the combinatorial aspects of the LINKAGE software.
• Evaluated the performance of these modifications on moderate and large-scale genetic datasets.
• Avoided the use of parallel computing, concentrating solely on algorithmic restructuring.

Main Results:

• Achieved order-of-magnitude speedups in genetic linkage analysis programs.
• Demonstrated significant performance enhancements on problems of moderate and large sizes.
• Validated the effectiveness of algorithmic modifications independent of parallel processing.

Conclusions:

• Algorithmic modifications offer a powerful, non-parallel approach to overcoming computational bottlenecks in genetic linkage analysis.
• The integration of biological principles with computer science techniques effectively restructures time-consuming computations.
• These improvements provide substantial speed gains, facilitating more efficient gene location studies.