High-performance implementation and analysis of the Linkmap program.

Linkage analysis uses information from family pedigrees to map genes and locate disease genes on particular chromosomes. A recombination fraction denoted as theta is estimated as a measure of crossing over between two loci. Genetic linkage calculations are very time-consuming particularly for large family pedigrees, a large number of theta values, and an increased number of markers. This paper reports the implementation of a dynamic master-slave scheme for the parallelization of the Linkmap program on a high-performance cluster such as the Origin 2000 (O2K) consisting of 56 R12000 processors. The Linkmap program is one of four programs in the LINKAGE/FASTLINK legacy package widely used by the medical research community. Implementations issues are addressed and results are compared with previous results on a cluster of DEC Alphas, and with the sequential execution on the O2K machine.

On the parallelization of linkmap from the LINKAGE/FASTLINK package.

Genetic linkage calculations can be time consuming, even on a fast computer. The ability to collect large family pedigrees has increased the magnitude of linkage computations. Sequential genetic algorithms have many successful applications in very different domains, but they have a main drawback in their utilization. Evaluations are very time-consuming, e.g., a pedigree consisting of 55 nodes takes about 70 min on a DEC-Alpha processor and about 270 min on a 166 MHz Pentium for certain likelihood calculations. This time increases exponentially with the increase in the size of the pedigree. In order to solve these shortcomings and to study new models of higher efficiency and efficacy, parallel platforms are being used for genetic programs. LINKAGE is a software package for performing genetic likelihood calculations; FASTLINK is an improved, faster version of it. This paper provides a parallel implementation of the "Linkmap" program (one of the four programs in LINKAGE/FASTLINK) for a heterogeneous environment, using a static and a dynamic strategy for task allocation. It was found that the increased performance by the dynamic strategy was close to the estimated maximum speed up.