AbstractRoutinely used multiple‐sequence alignment methods use only sequence information. Consequently, they may produce inaccurate alignments. Multiple‐structure alignment methods, on the other hand, optimize structural alignment by ignoring sequence information. Here, we present an optimization method that unifies sequence and structure information. The alignment score is based on standard amino acid substitution probabilities combined with newly computed three‐dimensional structure alignment probabilities. The advantage of our alignment scheme is in its ability to produce more accurate multiple alignments. We demonstrate the usefulness of the method in three applications: 1) computing more accurate multiple‐sequence alignments, 2) analyzing protein conformational changes, and 3) computation of amino acid structure‐sequence conservation with application to protein–protein docking prediction. The method is available athttp://bioinfo3d.cs.tau.ac.il/staccato/. Proteins 2006. © 2005 Wiley‐Liss, Inc.