Even though map construction using CEPH pedigrees or radiation hybrids can be fairly rapid when marker density is low, it is extremely time consuming to validate the map by using local permutations of loci to judge the likelihood of alternative maps. When marker density is high and when models are used that incorporate genotyping errors, mutations, sex-differences, and interference, current algorithms on serial processors are extremely slow. This is particularly so for constructing consensus maps. Our experience suggests an acute need for improved algorithms, and parallel and incremental algorithms have great promise in this regard. Finally, the dense marker maps generated by the Genome Project will ultimately be used to map loci involved in complex phenotypes. However, mapping complex phenotypes on pedigrees of arbitrary structure involves very difficult computations which will require the development of parallel and incremental algorithms, such as the ones proposed here. Therefore we plan to create new faster computational techniques that will permit more realistic and sophisticated analyses of larger data sets with less time and effort than are now possible.
The specific aims are: 1. To develop parallel computational techniques for multilocus linkage analysis and radiation hybrid mapping based on both large and fine grain parallelism. The resulting software will automatically partition the computational tasks of gene mapping across an appropriate selection of computers. 2. To use techniques of incremental processing to reduce the computational overhead for repeated likelihood calculations. 3. To apply the same techniques of parallel and incremental processing as described in Aims 1 and 2 to the locus ordering problem. This will include new parallel algorithms for locus ordering as well as more efficient implementations of well-known heuristic algorithms. 4. To explore genetic chaisma interference using marker data generated by our collaborators. We plan to modify our parallel likelihood algorithms described above to allow for interference. 5. To explore differences in male and female recombination fractions using marker data generated by our collaborators. This analysis may also lead to novel models of sex-differences. 6. To create an accessible national computing resource for geneticists. In the long term, the fast computational tools and the novel algorithms developed here will enable more rapid and accurate map construction and a deeper understanding of interference and recombination in humans.
Showing the most recent 10 out of 18 publications
