Dr. Suchendra M. Bhandarkar, Dept. of Computer Science
Dr. Jonathan Arnold, Dept. of Genetics
 
Project Description
 
    This project deals with the problem of physical mapping of chromosomes i.e., chromosome reconstruction from short DNA fragments (clones) and is in collaboration with the Department of Genetics. This project is funded by the Plant Genome Program of the US Department of Agriculture (USDA).
 
    Ordering clones from a genomic library into physical maps of whole chromosomes presents a central computational and statistical problem in genetics and is providing fundamental insights into development, gene organization, chromosome structure, recombination and the role of sex in evolution. Our research has shown the physical mapping problem to be isomorphic to the classical NP-complete Optimal Linear Arrangement (OLA) problem for which no polynomial time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques yielded very good results but were computationally intensive. The project aims to design, analyze and implement parallel algorithms to find high quality solutions to the physical mapping problem, align the physical maps with their corresponding genetics maps and assess the statistical reliability of physical maps in an expeditious manner.
 
    The specific goals of the project are:

1.  Design and analysis of parallel global optimization algorithms that are suitable for the assembly of physical maps from contig data;

2. Design and analysis of parallel boot-strap re-sampling algorithms for the statistical assessment of map reliability;

3. Design and analysis of parallel algorithms for alignment of physical maps with their corresponding genetic maps;

4. Implementation of the aforementioned parallel algorithms on prototypical Single Instruction Multiple Data (SIMD) and Multiple Instruction Multiple Data (MIMD) multiprocessor architectures and on a cluster of high-performance workstations;

5. Performance evaluation and bench marking of the parallel algorithms on clone/probe hybridization data sets from Aspergillus nidulans and Neurospora crassa.
 
    The outcome of the project will be a suite of parallel algorithms and programs that would enable timely generation of high quality physical maps, statistical assessment of the reliability of the physical maps and integration of the physical maps with their corresponding genetic maps. The resulting programs will be
incorporated in the Fungal Genome Database at the University of Georgia for use with an NSF funded robotics system for physical mapping of fungal genomes. The proposed research addresses the long-term goal of the USDA Plant Genome program of developing novel technologies for genome mapping, genome manipulation, gene isolation and gene transfer in plants. Physical maps of the fungal genomes A. nidulans and N. crassa fungi have not only led to fundamental advances in genetics, but also have an estimated economic impact of over $40 million/year through the mushroom industry, crop damage to peanuts, maize, and cotton, the processing of textiles, the manufacture of enzymes like amylase, and their role in the manufacture of various dairy products. More specifically, informatics and algorithmic tools for the generation of physical maps of the Aspergillus species will assist in the identification and manipulation of genes involved in aflatoxin production in peanuts, identification of signal transduction pathways for aflatoxin production, the identification of new targets for antifungal agents transformed into peanuts, and the differences between toxigenic and atoxigenic strains for the purposes of biocontrol.
 
Publications
 
S.M. Bhandarkar, S. Chirravuri, S. Machaka and J. Arnold, Parallel Computing for Chromosome Reconstruction via Ordering of DNA Sequences, Parallel Computing, Vol. 24, No. 8, 1998, pp. 1177-1204.
 
S.M. Bhandarkar, Parallel Processing for Chromosome Reconstruction from Physical Maps - A Case Study of MIMD Parallelism on the Hypercube, Parallel Algorithms and Applications, Vol. 12, 1997, pp. 231-252.
 
S.M. Bhandarkar and S. Machaka, Chromosome Reconstruction from Physical Maps Using a Cluster of Workstations, Journal of Supercomputing, Vol.  11, No. 1, 1997, pp. 61-86.
 
S.M. Bhandarkar, S. Chirravuri and J. Arnold, Parallel Computing of Physical Maps - A Comparative Study in SIMD and MIMD Parallelism, Journal of Computational Biology, Vol. 3, No. 4, 1996, pp. 503-528.
 
S.M. Bhandarkar and S. Chirravuri, A Study of Massively Parallel Simulated Annealing Algorithms for Chromosome Reconstruction via Clone Ordering, Parallel Algorithms and Applications, Vol. 9, 1996, pp. 67-89.
 
S.M. Bhandarkar, S. Chirravuri and J. Arnold, PARODS - A Study of Parallel Algorithms for Ordering DNA Sequences, Intl. Jour. Computer Appl. Bio.  Sci., Vol. 12, No. 4, 1996, pp. 269-280.
 
S.M. Bhandarkar and S.A. Machaka, Parallel Computing for Chromosome Reconstruction Using PVM, Proc. Intl. Conf. Parallel Dist. Proc. Tech. and Appl., Las Vegas, Nevada, July 1997, pp. 1567-1576.
 
S.M. Bhandarkar,  S. Chirravuri,  J. Arnold, and D. Whitmire, Massively Parallel Algorithms for Chromosome Reconstruction, Proc. Pacific Symp. on Biocomputing, Big Island, Hawaii,  Jan. 3-6, 1996, pp. 85-92.
 
S.M. Bhandarkar, Parallel Computation for Chromosome Reconstruction from Physical Maps, invited paper in Proc. First Intl. Conf. Neural, Parallel and Scientific Computing, Atlanta, GA, May 1995,  Vol. 1, pp. 49-52.
 
S.M. Bhandarkar and J. Arnold, Parallel Simulated Annealing on the Hypercube for Chromosome Reconstruction, invited paper in Proc. 14th IMACS World Congress on Computational and Applied Mathematics, Atlanta, GA, July  1994,  Vol. 3, pp. 1109-1112.