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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)


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
Title of host publication33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS 2011
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages4
ISBN (Print)9781424441211
Publication statusPublished - 26 Dec 2011
Externally publishedYes
EventInternational Conference of the IEEE Engineering in Medicine and Biology Society 2011 - Boston, United States of America
Duration: 30 Aug 20113 Sep 2011
Conference number: 33rd (Proceedings)


ConferenceInternational Conference of the IEEE Engineering in Medicine and Biology Society 2011
Abbreviated titleEMBC 2011
Country/TerritoryUnited States of America
Internet address

Cite this