Towards a HPC-oriented parallel implementation of a learning algorithm for bioinformatics applications

Area of Science:

• Computational Biology
• Bioinformatics
• Machine Learning

Background:

• Biomedical research generates vast datasets requiring advanced computational methods for analysis.
• High Performance Computing (HPC) offers solutions but faces challenges in parallelization and load balancing.
• The U-BRAIN algorithm, originally for DNA analysis, handles data with missing values but has high computational costs (O(n^5) time, O(n^3) memory).

Purpose of the Study:

• To develop an HPC-oriented parallel implementation of the U-BRAIN algorithm.
• To address the computational limitations of the serial U-BRAIN algorithm for large datasets.
• To optimize memory usage and execution time for the U-BRAIN algorithm.

Main Methods:

• Developed a Dynamic Programming model and minimized relevance representation for U-BRAIN.
• Designed a mass storage structure for efficient I/O and reduced communication costs.
• Implemented a parallel version using the SPMD model and Message-Passing Interface (MPI) via MPJ (Java).
• Organized parallel processing in four stages: partitioning, communication, agglomeration, and mapping.

Main Results:

• The parallel U-BRAIN model was implemented and tested on INTEL XEON processors within the EGI framework.
• Tested on IPDATA, HS3D, and COSMIC datasets, demonstrating reduced memory and execution time.
• Achieved optimal speed-up on IPDATA with approximately 90 processors, showing a direct relationship between data size and parallelization gain.
• The parallel version demonstrated up to 30 times faster performance compared to the serial version.

Conclusions:

• The parallel implementation of U-BRAIN effectively minimizes memory and execution time for large biomedical datasets.
• Performance gains are significant, with speed-up directly correlating with dataset size and processor count.
• The parallel U-BRAIN algorithm is a viable solution for accelerating complex data analysis in bioinformatics and related fields.