Henrik Haraldsson and Mattias Ohlsson A Fuzzy Matching Approach to Multiple Structure Alignment of Proteins Abstract Motivation: Comparing protein structures is important for understanding the relationships between sequence, structure and function. With the increasing number of experimentally determined protein structures, an automated algorithm that can perform structure alignment of many proteins is therefore highly advantageous. Results: We present a novel approach for multiple structure alignment of proteins based on fuzzy pairwise alignments of each protein to a virtual consensus chain. These alignments are alternated with translations and rotations of the proteins onto the consensus structure, and with updating each consensus atom by moving it to the middle of the protein atoms aligned to it. The pairwise alignments use mean-field annealing optimization of fuzzy alignment variables, based on a cost expressed in terms of distances between aligned atoms and of gaps. No initialization in terms of all-to-all protein alignments is needed, and the only information required is the 3-D coordinates of the $C_\alpha$ atoms. The CPU consumption is modest, and scales approximately linearly with the number of proteins to align. Our approach is tested against a set of protein families from the \textsc{Homstrad} database, and against a multiple structure alignment algorithm based on Monte Carlo techniques, with good results. LU TP 03-17