Frost: Revisited and distributed

FROST (Fold Recognition-Oriented Search Tool) [6] is a software whose purpose is to assign a 3D structure to a protein sequence. It is based on a series of filters and uses a database of about 1200 known 3D structures, each one associated with empirically determined score distributions. FROST uses these distributions to normalize the score ob-tained when a protein sequence is aligned with a particu-lar 3D structure. Computing these distributions is extremely time consuming; it requires solving about 1; 200; 000 hard combinatorial optimization problems and takes about 40 days on a 2.4 GHz computer. This paper describes how FROST has been successfully redesigned and structured in modules and independent tasks. The new package organi-zation allows these tasks to be distributed and executed in parallel using a centralized dynamic load balancing strat-egy. On a cluster of 12 PCs, computing the score distribu-tions takes now about 3 days which represents a paralleliza-tion efficiency of about 1. Key words: protein threading; parallel algorithms; large scale problems; 1