Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers

Philip C. Church*, Andrzej Goscinski, Kathryn Holt, Michael Inouye, Amol Ghoting, Konstantin Makarychev, Matthias Reumann

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

The challenge of comparing two or more genomes that have undergone recombination and substantial amounts of segmental loss and gain has recently been addressed for small numbers of genomes. However, datasets of hundreds of genomes are now common and their sizes will only increase in the future. Multiple sequence alignment of hundreds of genomes remains an intractable problem due to quadratic increases in compute time and memory footprint. To date, most alignment algorithms are designed for commodity clusters without parallelism. Hence, we propose the design of a multiple sequence alignment algorithm on massively parallel, distributed memory supercomputers to enable research into comparative genomics on large data sets. Following the methodology of the sequential progressiveMauve algorithm, we design data structures including sequences and sorted k-mer lists on the IBM Blue Gene/P supercomputer (BG/P). Preliminary results show that we can reduce the memory footprint so that we can potentially align over 250 bacterial genomes on a single BG/P compute node. We verify our results on a dataset of E.coli, Shigella and S.pneumoniae genomes. Our implementation returns results matching those of the original algorithm but in 1/2 the time and with 1/4 the memory footprint for scaffold building. In this study, we have laid the basis for multiple sequence alignment of large-scale datasets on a massively parallel, distributed memory supercomputer, thus enabling comparison of hundreds instead of a few genome sequences within reasonable time.

Original languageEnglish (US)
Title of host publication33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011
Pages924-927
Number of pages4
DOIs
StatePublished - Dec 26 2011
Event33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011 - Boston, MA, United States
Duration: Aug 30 2011Sep 3 2011

Publication series

NameProceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS
ISSN (Print)1557-170X

Conference

Conference33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011
CountryUnited States
CityBoston, MA
Period8/30/119/3/11

ASJC Scopus subject areas

  • Signal Processing
  • Biomedical Engineering
  • Computer Vision and Pattern Recognition
  • Health Informatics

Fingerprint Dive into the research topics of 'Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers'. Together they form a unique fingerprint.

  • Cite this

    Church, P. C., Goscinski, A., Holt, K., Inouye, M., Ghoting, A., Makarychev, K., & Reumann, M. (2011). Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers. In 33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011 (pp. 924-927). [6090208] (Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS). https://doi.org/10.1109/IEMBS.2011.6090208