Alignment of multiple protein structures is a fundamental problem in structural genomics and it is crucial for many purposes in biology, including the study of evolution in protein families, identification of patterns of conservation in sequences that fold into similar structures, homology modelling and protein crystal structure solution by molecular replacement. Our recent proposed and published algorithm named MUSTANG (MUltiple STructural AligNment AlGorithm) achieves impressive accuracy. Broadly based on the progressive pairwise heuristic and benefits from an effective refinement phase, MUSTANG is very reliable in generating quality multiple structural alignment results even on very distantly-related data sets containing structural deformations.

Because of its fundamental role in biology and its accuracy in aligning both closely and distantly related structures, the biology community has quickly accepted MUSTANG since it was published in August, 2006. Several research groups from different organizations around the world currently use the sequential software implementation of the MUSTANG. However, the MUSTANG algorithm comes with the challenge that the run time is typically long on normal PCs when aligning many distantly related structures.

The project aims to provide a high performance parallel implementation of the MUSTANG algorithm for clusters and SMP systems. Our preliminary parallel version of MUSTANG demonstrates linear speedup on our departmental small scale networked workstations.

By increasing the throughput of MUSTANG using parallelisation, MUSTANG will be further used to provide a sensitive protein database lookup process.

Specifically, the outcome of our proposed project will be:

• Parallelised MUSTANG algorithm and the implementations for both clusters and SMP systems. A user-friendly web-portal that allows users to easily access the system without the knowledge about the underlying hardware.

• Design and implementation of our efficient protein database lookup system using parallelised MUSTANG algorithm.

---

This project is in collaboration with colleagues at University of Melbourne (Dr. Aaron Harwood and Prof. Peter J. Stuckey)

---