Name
Abstract | ||
|---|---|---|
Pairwise structure alignment commonly uses root mean square deviation (RMSD) to measure the structural similarity, and methods for optimizing RMSD are well established. However, multiple structure alignment with gaps cannot use these methods directly. We extend RMSD to weighted RMSD for multiple structures, which includes gapped alignment as a special case. By using multiplicative weights, we show that weighted RMSD for all pairs is the same as weighted RMSD to an average of the structures. Although we show that the two tasks of finding the optimal translations and rotations for minimizing weighted RMSD cannot be separated for multiple structures like they can for pairs, an inherent difficulty and a fact ignored by previous work, we develop an iterative algorithm, in which each iteration takes linear time and the number of iterations is small, to converge weighted RMSD to a local minimum. 10,000 experiments done on each of 23 protein families from HOMSTRAD (where each structure starts with a random translation and rotation) converge rapidly to the same minimum. Finally we propose a heuristic method to iteratively remove the effect of outliers and find well-aligned positions that determine the structural conserved region by modeling B-factors and deviations from the average positions as weights and iteratively assigning higher weights to better aligned atoms. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74126-8_19 | WABI |
Keywords | Field | DocType |
multiple structure alignment,pairwise structure alignment,weighted rmsd,structural similarity,optimum rmsd,average position,optimizing rmsd,multiple structure,gapped multiple structure alignment,structural conserved region,gapped alignment,local minimum,structure alignment,linear time,protein family,iterative algorithm,root mean square deviation | Pairwise comparison,Combinatorics,Heuristic,Structural alignment,Multiplicative function,Iterative method,Outlier,Root-mean-square deviation,Time complexity,Mathematics | Conference |
Volume | ISSN | ISBN |
4645 | 0302-9743 | 3-540-74125-9 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xueyi Wang | 1 | 138 | 13.79 |
| Jack Snoeyink | 2 | 2842 | 231.68 |