BACKGROUND
this paper presents an algorithm to compute a multiple structure alignment for a set of proteins and to generate a consensus structure.
the algorithm is called mapsci, which stands for multiple alignment of protein structures and consensus identification.
mapsci addresses the problem of global structure alignment, which has also been considered by ce-mc  <cit> , mammoth  <cit> , and matt  <cit> .
specifically, mapsci computes an approximation to the multiple structure alignment that minimizes the so-called sum-of-consensus distance , i.e.
the sum of the pairwise distances between the consensus structure and each protein in the set .
our experiments show that mapsci converges quite rapidly and produces alignments that compare favorably with the alignments produced by mammoth and matt.
the consensus structures generated by mapsci are visually quite similar to the input proteins.
although the consensus structures are not real proteins, they could be used, for instance, as templates to perform fast searches through protein structure databases, such as the protein data dank  <cit> , to identify structurally similar proteins.
mapsci has similar structure to the algorithm of ye and janardan  <cit> .
however, mapsci works directly on the coordinates of the cα atoms and produces true alignments; by contrast, the algorithm in  <cit>  requires that the backbone vectors be translated to the origin, hence information about the relative positions of the cα atoms in ℝ <dig> is lost and as a result the algorithm does not generate true alignments.
the methods section presents the mathematical and algorithmic framework of mapsci and provides the complete details where the two algorithms differ significantly; when there is an overlap the reader is referred to publication  <cit> .
implementation
mapsci represents the input proteins and the consensus as sequences of triples of coordinates of the alpha-carbon  atoms along the backbone.
it then computes a correspondence between the coordinate triples of the cα atoms in the different protein structures by choosing one of the proteins as the initial consensus and applying an algorithm that is analogous to the center-star method for multiple sequence alignment  <cit> .
next, mapsci derives a set of translation and rotation matrices that are optimal for the computed correspondence and uses these to align the structures in space via rigid motions and obtain the new consensus.
the process is repeated until the change in sc-distance is less than a prescribed threshold.
this iterative process is well-defined as it is shown in the methods section that the sc-distance is non-increasing from one iteration to the next.
the computation of the optimal translations and rotations and the new consensus is itself an iterative process that both uses the current consensus and generates simultaneously a new one.
RESULTS
web server
mapsci has been incorporated into a web server for remote access over the internet .
this tool allows for protein structures to be uploaded from files on the local disk or retrieved from the protein data bank   <cit>  by specifying their pdb ids.
the results from the alignment are annotated in the standard nbrf/pir format, which can be previewed online via the jalview applet  <cit> .
integrated with the server is the molecular viewer applet chemis 3d  <cit> , which allows for visualization of the aligned protein structures.
the web server offers a simple interface that allows for remote access from within other software.
table  <dig> gives an example of using the programming language python to retrieve the transformed coordinates  for the multiple alignment of the structures from the homstrad cub family.
additional examples and the complete set of options for remote access can be found at the server web page .
an example of using the programming language python to retrieve the transformed coordinates  for the multiple alignment of the structures from the homstrad cub family.
additional examples and the complete set of options for remote access can be found at the server web page .
comparison
as discussed earlier, there are many algorithms for multiple structure alignment.
in general, it is difficult to make comparisons among them, since they operate under different sets of assumptions and problem formulations.
we compare mapsci to two recent algorithms -- mammoth  <cit>  and matt  <cit>  -- which also work with coordinate triples, but employ a different objective function.
our experiments show that mapsci is competitive in terms of the sizes of the so-called conserved regions and runs significantly faster than the other two algorithms, hence can potentially scale to much larger datasets.
the comparison is based on two benchmark datasets.
the first dataset is compiled from the homstrad database  <cit> , which is a curated database of structure-based alignments for homologous protein families and is considered the "gold" standard.
the benchmark dataset consists of the  <dig> homstrad families that have at least  <dig> structures.
the second dataset consists of the superfamily set in the sabmark database  <cit>  .
it contains  <dig> families with low to intermediate sequence similarity.
the metrics considered in the comparison are the strict core  and the core rmsd.
this follows the experimental setup in  <cit>  where strict core is defined as "the set of positions with 100% conservation, and within  <dig>  Å of each other in the final structural alignment in 3d".
a similar metric is discussed in  <cit>  and  <cit> .
the results are summarized in figures  <dig> and  <dig>  which show the pairwise comparisons ,  in terms of the core size  and the core rmsd.
table  <dig> provides a comparison of the average core size and average core rmsd for the three methods on the benchmark datasets.
statistics for the performance of the three methods on the benchmark datasets.
the subscripts in the average core rmsd columns indicate how many values were used in computing the statistics, since the algorithms failed to compute a core for some of the data sets.
for the average core  columns all reported values were used and therefore n =  <dig> and n =  <dig> for the homstrad and sabmark datasets, respectively.
in general, it is difficult to compare two algorithms based on these two metrics .
however, on the homstrad dataset mapsci outperformed mammoth in 45% of the test cases and matt in 59% of the test cases by computing alignments with both larger cores and smaller core rmsd.
.
mapsci computed cores for all  <dig> test cases, while mammoth failed to compute a core for one family , and matt failed to compute a core for three families .
on the sabmark dataset mapsci computed larger cores with better rmsd in 39% of the test cases when compared with mammoth and in 37% of the test cases against against matt.
matt was the most robust of the three algorithms and failed to compute a core in only five test cases; mapsci failed on  <dig> families and mammoth failed on  <dig> families.
mapsci took only  <dig> seconds to align the  <dig> families in the sabmark dataset and  <dig> seconds to align the families in the homstrad dataset.
mammoth took  <dig> seconds on the sabmark dataset and  <dig> seconds on the homstrad dataset.
by contrast, matt took several hours to process the two datasets.
figure  <dig> shows the actual time taken by mapsci for all families in the benchmark dataset in terms of the total number of residues per family.
the algorithm converges very quickly and can potentially scale to large datasets.
the machine used for all experiments reported in the paper runs ubuntu linux  <dig>  and has  <dig> gb of ram with intel®core™ <dig> quad cpu q <dig> @  <dig>  ghz.
mammoth and matt were run with their default parameter settings.
methods
in this section, we provide the mathematical and algorithmic framework underlying mapsci.
as mentioned earlier mapsci shares common elements with the algorithm in  <cit> , and therefore, we follow the same general outline.
however, we only present the full details when there are significant differences and refer the reader to  <cit>  when there is an overlap.
multiple structure alignment: problem formulation
let {p <dig>  p <dig>  ⋯, pk} be the given set of k proteins and let li be the number of cα atoms along the backbone of protein pi.
we represent pi as a sequence of coordinate triples ,  <dig> ≤ j ≤ li, that represent the coordinates of the jth cα atom of pi along the backbone.
let p <dig> = , ⋯,  denote the consensus structure, of length l <dig>
a correspondence of the k proteins in  and the consensus structure p <dig> can be represented as a matrix h = () <dig> ≤ i ≤ k, <dig> ≤ j ≤ l, for some l ≥ max <dig> ≤ i ≤ k{li}, where  is either a coordinate triple belonging to the ith protein or a gap.
distances between coordinate triples are based on the squared distance between them in ℝ <dig>  the distance between a coordinate triple and a gap is called a gap penalty, and is denoted by ρ.
the results reported in this paper use  <dig>  for the value of the gap penalty.
let gi = ri = ri, for i > <dig>  where ri ∈ ℝ <dig> ×  <dig> is some rotation matrix, ti = e ×  is the translation matrix, e ∈ ℝl ×  <dig> is a vector with  <dig> in each entry, and  ∈ ℝ <dig> ×  <dig> is a translation vector.
note that p <dig> remains unchanged, i.e.
g <dig> = h <dig>
under the multiple structure alignment we define the distance between the consensus structure p <dig> and protein pj as , where d denotes the following distance function:
the distance between p <dig> and pj can be represented compactly as , where ||·||f denotes the frobenius norm  <cit> , with the additional convention that the squared difference between a coordinate triple and a gap is ρ <dig>  the total distance of the k proteins to the consensus structure, called the sum-of-consensus distance, or sc-distance, is then defined as
intuitively, the sc-distance measures how well the consensus structure represents the given set of k proteins.
a similar distance function is used in  <cit> , where each protein is represented as a set of vectors in ℝ <dig>
we can now define the multiple structure alignment problem as follows:
multiple structure alignment problem
given a set {p <dig>  p <dig>  ⋯, pk} of protein structures, compute a transformation  for each protein, and generate a consensus structure p <dig>  such that the resulting multiple structure alignment has minimum sc-distance as defined in equation .
in the next section, we present a heuristic for this problem.
our algorithm approximates the global minimum of the sc-distance by iterative refinement of an initial multiple structure alignment and converges to a local minimum.
step i: choice of the initial consensus structure
we consider four choices for initial consensus structure:  median protein, i.e.
the protein of median length;  center protein, i.e.
the protein that minimizes the sum of the pairwise distances to all the other proteins;  the minmax protein, i.e.
the protein with the smallest maximum pairwise distance; and  maxcore protein, i.e.
the protein that generates the largest initial core.
the experimental results in figure  <dig> indicate that mapsci is quite robust in terms of the choice of initial consensus.
however, the data suggests that the median protein occasionally leads to alignments with very low core size, and therefore is the least reliable choice.
the other three choices seem to work well in practice, although they are more expensive computationally.
the results reported in the comparison section use the maxcore protein as the initial consensus.
step ii: compute an initial correspondence
after we determine the consensus structure p <dig> in step i, the k -  <dig> pairwise structure alignments between p <dig> and pi ≠ p <dig>  for i =  <dig>  ⋯, k, are computed using the algorithm in  <cit> .
the k -  <dig> pairwise structure are combined in line  <dig> of the algorithm  using the center-star-like method described in  <cit> .
step iii: compute optimal rotation and translation matrices and consensus structure
given a correspondence h = () the objective is to find the rotation and translation matrices rj and tj, for j =  <dig>  ⋯, k, and the consensus structure , such that the sum of the pairwise alignment distances between  and each  pj is minimum; i.e.
we wish to minimize
direct minimization of s over , and the tj's and rj's seems difficult.
instead, we propose an iterative procedure for minimizing s. within each iteration, the minimization of s is carried out in two stages that are interleaved:  computation of the optimal  for given rj's and tj's, and  computation of the optimal rj's and tj's for a given .
computation of the optimal consensus structure
first, we show how to compute the consensus structure, given the rotation and translation matrices rj's and tj's, as stated in the following theorem:
theorem  <dig>  assume that the correspondence is represented as a matrix h = () and  = t is the optimal consensus structure.
for each column j, let in be the set of indices of proteins with a non-gap in the jth column and ig be the set of indices of proteins with a gap in the jth column.
then , in the jth position of the optimal consensus structure equals either the coordinate triple , or a gap.
proof.
for each j, we consider two distinct cases for jj: either it is a coordinate triple, x, or a gap.
if jj is a gap, then the sum of the distances between  and each protein pj along the jth column is |in|ρ <dig>  where ρ is the gap penalty.
if jj is a coordinate triple, x, then the sum of the distances between  and each protein pj along the jth column is , which is minimized, for .
therefore, if , then the optimal choice for  is the coordinate triple xj; otherwise, the optimal choice for  is a gap.
computation of the optimal translation matrix
in this section, we show how to compute the optimal translation matrix ti, for each i, for a given consensus structure .
from eq.
, it is clear that the optimal ti and tj, for i ≠ j are independent of each other.
hence, in the following, we focus on the computation of ti, for a specific i. the translation matrix ti can be decomposed as ti = e × ti, where ti ∈ r <dig> ×  <dig> is the translation vector.
as mentioned earlier, the transformation of a gap remains a gap.
hence the computation of the translation and rotation matrices is independent of the mismatches .
we can thus simplify the computation by removing all mismatches in the alignment between the consensus structure  and the ith protein pi.
let a ∈ ℝn ×  <dig> and b ∈ ℝn ×  <dig> consist of the coordinate triples from the consensus structure and the ith protein, respectively, after removing the mismatches.
.
without loss of generality, assume eta =  <cit> , i.e., the coordinate triples in the consensus protein are centered at the origin.
the optimal translation vector is the one that matches the centroids of the coordinate triple vectors from a and b as stated in the following theorem:
theorem  <dig>  let a and b be defined as above.
assume that eta =  <cit> .
then for any rotation matrix ri, the optimal translation vector ti for minimizing is given by .
more details can be found in  <cit> .
computation of the optimal rotation matrix
next, consider the rotation matrix ri.
we can assume that the coordinate triple vectors from both a and b are centered at the origin.
it follows that
hence the minimum of si is obtained when trace  is maximized.
let the singular value decomposition   <cit>  of atb be uΣvt, where u and v are orthogonal and Σ is diagonal.
theorem  <dig>  the optimal rotation matrix ri that minimizes si = ||a - bri|| <dig> is given by ri = uwvt, where w = diag, if det =  <dig>  and w = diag, if det = - <dig>
more details can be found in  <cit> .
convergence of the algorithm
in this section, we show that mapsci converges, by showing that the sc-distance is non-increasing from one iteration to the next.
recall that from eq.
,
line  <dig> in mapsci decreases the distance between the consensus structure and each of the k proteins, since the dynamic programming produces an alignment with minimum cost.
by the property of the center-star-like method, line  <dig> leaves unchanged the distance between the consensus structure and each of the k proteins.
by theorems  <dig> and  <dig>  the transformations computed in line  <dig> do not increase the distance between the consensus structure and the jth protein, for each j. it is clear that line  <dig> does not change the pairwise distance, since the cost for aligning two gaps is zero.
finally, by theorem  <dig>  line  <dig> does not increase the sum of the pairwise distances from the consensus structure to the other proteins.
hence, the sc-distance is non-increasing, and the algorithm converges.
complexity analysis
let n be the maximum length of the k proteins.
then the overall running time of the algorithm is o.
.)
the run time analysis is similar to that of the algorithm in  <cit> .
CONCLUSIONS
we have presented an algorithm, called mapsci, to compute a multiple structure alignment for a set of proteins, together with their consensus structure.
the algorithm represents the input proteins and the consensus as sequences of coordinate triples and computes an approximation to the optimal multiple structure alignment that minimizes the sum of the pairwise distances between the consensus and each input protein.
experimental results on a benchmark datasets derived from the homstrad and sabmark databases show that the algorithm compares favorably with existing algorithms for multiple structure alignment .
availability and requirements
• project name: mapsci
• project home page: http://www.geom-comp.umn.edu/mapsci
• operating system: platform-independent
• programming language: c++
• license: free bsd
authors' contributions
jy contributed to the design of the algorithm and experiments, and drafting of the manuscript.
ii contributed to the experiments and the implementation of the algorithm.
rj contributed to the refinement of the algorithm and drafting of the manuscript.
all authors read and approved the final manuscript.

 this paper presents an algorithm to compute a multiple structure alignment for a set of proteins and to generate a consensus structure. the algorithm is called mapsci, which stands for multiple alignment of protein structures and consensus identification. mapsci addresses the problem of global structure alignment, which has also been considered by ce-mc, mammoth, and matt. specifically, mapsci computes an approximation to the multiple structure alignment that minimizes the so-called sum-of-consensus distance, i.e. the sum of the pairwise distances between the consensus structure and each protein in the set. our experiments show that mapsci converges quite rapidly and produces alignments that compare favorably with the alignments produced by mammoth and matt. the consensus structures generated by mapsci are visually quite similar to the input proteins. although the consensus structures are not real proteins, they could be used, for instance, as templates to perform fast searches through protein structure databases, such as the protein data dank, to identify structurally similar proteins. mapsci has similar structure to the algorithm of ye and janardan. however, mapsci works directly on the coordinates of the cα atoms and produces true alignments; by contrast, the algorithm in requires that the backbone vectors be translated to the origin, hence information about the relative positions of the cα atoms in ℝ is lost and as a result the algorithm does not generate true alignments. the methods section presents the mathematical and algorithmic framework of mapsci and provides the complete details where the two algorithms differ significantly; when there is an overlap the reader is referred to publication. implementation mapsci represents the input proteins and the consensus as sequences of triples of coordinates of the alpha-carbon atoms along the backbone. it then computes a correspondence between the coordinate triples of the cα atoms in the different protein structures by choosing one of the proteins as the initial consensus and applying an algorithm that is analogous to the center-star method for multiple sequence alignment. next, mapsci derives a set of translation and rotation matrices that are optimal for the computed correspondence and uses these to align the structures in space via rigid motions and obtain the new consensus. the process is repeated until the change in sc-distance is less than a prescribed threshold. this iterative process is well-defined as it is shown in the methods section that the sc-distance is non-increasing from one iteration to the next. the computation of the optimal translations and rotations and the new consensus is itself an iterative process that both uses the current consensus and generates simultaneously a new one.  web server mapsci has been incorporated into a web server for remote access over the internet. this tool allows for protein structures to be uploaded from files on the local disk or retrieved from the protein data bank by specifying their pdb ids. the results from the alignment are annotated in the standard nbrf/pir format, which can be previewed online via the jalview applet. integrated with the server is the molecular viewer applet chemis 3d, which allows for visualization of the aligned protein structures. the web server offers a simple interface that allows for remote access from within other software. table gives an example of using the programming language python to retrieve the transformed coordinates for the multiple alignment of the structures from the homstrad cub family. additional examples and the complete set of options for remote access can be found at the server web page. an example of using the programming language python to retrieve the transformed coordinates for the multiple alignment of the structures from the homstrad cub family. additional examples and the complete set of options for remote access can be found at the server web page. comparison as discussed earlier, there are many algorithms for multiple structure alignment. in general, it is difficult to make comparisons among them, since they operate under different sets of assumptions and problem formulations. we compare mapsci to two recent algorithms -- mammoth and matt -- which also work with coordinate triples, but employ a different objective function. our experiments show that mapsci is competitive in terms of the sizes of the so-called conserved regions and runs significantly faster than the other two algorithms, hence can potentially scale to much larger datasets. the comparison is based on two benchmark datasets. the first dataset is compiled from the homstrad database, which is a curated database of structure-based alignments for homologous protein families and is considered the "gold" standard. the benchmark dataset consists of the homstrad families that have at least structures. the second dataset consists of the superfamily set in the sabmark database. it contains families with low to intermediate sequence similarity. the metrics considered in the comparison are the strict core and the core rmsd. this follows the experimental setup in where strict core is defined as "the set of positions with 100% conservation, and within Å of each other in the final structural alignment in 3d". a similar metric is discussed in and. the results are summarized in figures and which show the pairwise comparisons, in terms of the core size and the core rmsd. table provides a comparison of the average core size and average core rmsd for the three methods on the benchmark datasets. statistics for the performance of the three methods on the benchmark datasets. the subscripts in the average core rmsd columns indicate how many values were used in computing the statistics, since the algorithms failed to compute a core for some of the data sets. for the average core columns all reported values were used and therefore n = and n = for the homstrad and sabmark datasets, respectively. in general, it is difficult to compare two algorithms based on these two metrics. however, on the homstrad dataset mapsci outperformed mammoth in 45% of the test cases and matt in 59% of the test cases by computing alignments with both larger cores and smaller core rmsd.. mapsci computed cores for all test cases, while mammoth failed to compute a core for one family, and matt failed to compute a core for three families. on the sabmark dataset mapsci computed larger cores with better rmsd in 39% of the test cases when compared with mammoth and in 37% of the test cases against against matt. matt was the most robust of the three algorithms and failed to compute a core in only five test cases; mapsci failed on families and mammoth failed on families. mapsci took only seconds to align the families in the sabmark dataset and seconds to align the families in the homstrad dataset. mammoth took seconds on the sabmark dataset and seconds on the homstrad dataset. by contrast, matt took several hours to process the two datasets. figure shows the actual time taken by mapsci for all families in the benchmark dataset in terms of the total number of residues per family. the algorithm converges very quickly and can potentially scale to large datasets. the machine used for all experiments reported in the paper runs ubuntu linux and has gb of ram with intel®core™ quad cpu q @ ghz. mammoth and matt were run with their default parameter settings. methods in this section, we provide the mathematical and algorithmic framework underlying mapsci. as mentioned earlier mapsci shares common elements with the algorithm in, and therefore, we follow the same general outline. however, we only present the full details when there are significant differences and refer the reader to when there is an overlap. multiple structure alignment: problem formulation let {p p ⋯, pk} be the given set of k proteins and let li be the number of cα atoms along the backbone of protein pi. we represent pi as a sequence of coordinate triples, ≤ j ≤ li, that represent the coordinates of the jth cα atom of pi along the backbone. let p =, ⋯, denote the consensus structure, of length l a correspondence of the k proteins in and the consensus structure p can be represented as a matrix h = () ≤ i ≤ k, ≤ j ≤ l, for some l ≥ max ≤ i ≤ k{li}, where is either a coordinate triple belonging to the ith protein or a gap. distances between coordinate triples are based on the squared distance between them in ℝ the distance between a coordinate triple and a gap is called a gap penalty, and is denoted by ρ. the results reported in this paper use for the value of the gap penalty. let gi = ri = ri, for i > where ri ∈ ℝ × is some rotation matrix, ti = e × is the translation matrix, e ∈ ℝl × is a vector with in each entry, and ∈ ℝ × is a translation vector. note that p remains unchanged, i.e. g = h under the multiple structure alignment we define the distance between the consensus structure p and protein pj as, where d denotes the following distance function: the distance between p and pj can be represented compactly as, where ||·||f denotes the frobenius norm, with the additional convention that the squared difference between a coordinate triple and a gap is ρ the total distance of the k proteins to the consensus structure, called the sum-of-consensus distance, or sc-distance, is then defined as intuitively, the sc-distance measures how well the consensus structure represents the given set of k proteins. a similar distance function is used in, where each protein is represented as a set of vectors in ℝ we can now define the multiple structure alignment problem as follows: multiple structure alignment problem given a set {p p ⋯, pk} of protein structures, compute a transformation for each protein, and generate a consensus structure p such that the resulting multiple structure alignment has minimum sc-distance as defined in equation. in the next section, we present a heuristic for this problem. our algorithm approximates the global minimum of the sc-distance by iterative refinement of an initial multiple structure alignment and converges to a local minimum. step i: choice of the initial consensus structure we consider four choices for initial consensus structure: median protein, i.e. the protein of median length; center protein, i.e. the protein that minimizes the sum of the pairwise distances to all the other proteins; the minmax protein, i.e. the protein with the smallest maximum pairwise distance; and maxcore protein, i.e. the protein that generates the largest initial core. the experimental results in figure indicate that mapsci is quite robust in terms of the choice of initial consensus. however, the data suggests that the median protein occasionally leads to alignments with very low core size, and therefore is the least reliable choice. the other three choices seem to work well in practice, although they are more expensive computationally. the results reported in the comparison section use the maxcore protein as the initial consensus. step ii: compute an initial correspondence after we determine the consensus structure p in step i, the k - pairwise structure alignments between p and pi ≠ p for i = ⋯, k, are computed using the algorithm in. the k - pairwise structure are combined in line of the algorithm using the center-star-like method described in. step iii: compute optimal rotation and translation matrices and consensus structure given a correspondence h = () the objective is to find the rotation and translation matrices rj and tj, for j = ⋯, k, and the consensus structure, such that the sum of the pairwise alignment distances between and each pj is minimum; i.e. we wish to minimize direct minimization of s over, and the tj's and rj's seems difficult. instead, we propose an iterative procedure for minimizing s. within each iteration, the minimization of s is carried out in two stages that are interleaved: computation of the optimal for given rj's and tj's, and computation of the optimal rj's and tj's for a given. computation of the optimal consensus structure first, we show how to compute the consensus structure, given the rotation and translation matrices rj's and tj's, as stated in the following theorem: theorem assume that the correspondence is represented as a matrix h = () and = t is the optimal consensus structure. for each column j, let in be the set of indices of proteins with a non-gap in the jth column and ig be the set of indices of proteins with a gap in the jth column. then, in the jth position of the optimal consensus structure equals either the coordinate triple, or a gap. proof. for each j, we consider two distinct cases for jj: either it is a coordinate triple, x, or a gap. if jj is a gap, then the sum of the distances between and each protein pj along the jth column is |in|ρ where ρ is the gap penalty. if jj is a coordinate triple, x, then the sum of the distances between and each protein pj along the jth column is, which is minimized, for. therefore, if, then the optimal choice for is the coordinate triple xj; otherwise, the optimal choice for is a gap. computation of the optimal translation matrix in this section, we show how to compute the optimal translation matrix ti, for each i, for a given consensus structure. from eq., it is clear that the optimal ti and tj, for i ≠ j are independent of each other. hence, in the following, we focus on the computation of ti, for a specific i. the translation matrix ti can be decomposed as ti = e × ti, where ti ∈ r × is the translation vector. as mentioned earlier, the transformation of a gap remains a gap. hence the computation of the translation and rotation matrices is independent of the mismatches. we can thus simplify the computation by removing all mismatches in the alignment between the consensus structure and the ith protein pi. let a ∈ ℝn × and b ∈ ℝn × consist of the coordinate triples from the consensus structure and the ith protein, respectively, after removing the mismatches.. without loss of generality, assume eta =, i.e., the coordinate triples in the consensus protein are centered at the origin. the optimal translation vector is the one that matches the centroids of the coordinate triple vectors from a and b as stated in the following theorem: theorem let a and b be defined as above. assume that eta =. then for any rotation matrix ri, the optimal translation vector ti for minimizing is given by. more details can be found in. computation of the optimal rotation matrix next, consider the rotation matrix ri. we can assume that the coordinate triple vectors from both a and b are centered at the origin. it follows that hence the minimum of si is obtained when trace is maximized. let the singular value decomposition of atb be uΣvt, where u and v are orthogonal and Σ is diagonal. theorem the optimal rotation matrix ri that minimizes si = ||a - bri|| is given by ri = uwvt, where w = diag, if det = and w = diag, if det = - more details can be found in. convergence of the algorithm in this section, we show that mapsci converges, by showing that the sc-distance is non-increasing from one iteration to the next. recall that from eq., line in mapsci decreases the distance between the consensus structure and each of the k proteins, since the dynamic programming produces an alignment with minimum cost. by the property of the center-star-like method, line leaves unchanged the distance between the consensus structure and each of the k proteins. by theorems and the transformations computed in line do not increase the distance between the consensus structure and the jth protein, for each j. it is clear that line does not change the pairwise distance, since the cost for aligning two gaps is zero. finally, by theorem line does not increase the sum of the pairwise distances from the consensus structure to the other proteins. hence, the sc-distance is non-increasing, and the algorithm converges. complexity analysis let n be the maximum length of the k proteins. then the overall running time of the algorithm is o..) the run time analysis is similar to that of the algorithm in.  we have presented an algorithm, called mapsci, to compute a multiple structure alignment for a set of proteins, together with their consensus structure. the algorithm represents the input proteins and the consensus as sequences of coordinate triples and computes an approximation to the optimal multiple structure alignment that minimizes the sum of the pairwise distances between the consensus and each input protein. experimental results on a benchmark datasets derived from the homstrad and sabmark databases show that the algorithm compares favorably with existing algorithms for multiple structure alignment. availability and requirements • project name: mapsci • project home page: http://www.geom-comp.umn.edu/mapsci • operating system: platform-independent • programming language: c++ • license: free bsd authors' contributions jy contributed to the design of the algorithm and experiments, and drafting of the manuscript. ii contributed to the experiments and the implementation of the algorithm. rj contributed to the refinement of the algorithm and drafting of the manuscript. all authors read and approved the final manuscript. 
alternatively, the algorithm can be used via a web server which makes it possible to align protein structures by uploading files from local disk or by downloading protein data from the rcsb protein data bank. the algorithm is a heuristic in that it computes an approximation to the optimal alignment that minimizes the sum of the pairwise distances between the consensus and the transformed proteins. an algorithm is presented to compute a multiple structure alignment for a set of proteins and to generate a consensus protein which captures common substructures present in the given proteins. an algorithm is presented to compute a multiple structure alignment for a set of proteins, together with their consensus structure. experimental results show that the algorithm converges quite rapidly and generates consensus structures that are visually similar to the input proteins. experimental results show its effectiveness in terms of the quality of the alignment and computational cost. the algorithm represents each protein as a sequence of triples of coordinates of the alpha-carbon atoms along the backbone. a comparison with other coordinate-based alignment algorithms shows that the proposed algorithm is competitive in terms of speed and the sizes of the conserved regions discovered in an extensive benchmark dataset derived from the homstrad and sabmark databases.
 an algorithm is presented to compute a multiple structure alignment for a set of proteins and to generate a consensus protein which captures common substructures present in the given proteins. the algorithm represents each protein as a sequence of triples of coordinates of the alpha-carbon atoms along the backbone. it then computes iteratively a sequence of transformation matrices to align the proteins in space and generate the consensus. the algorithm is a heuristic in that it computes an approximation to the optimal alignment that minimizes the sum of the pairwise distances between the consensus and the transformed proteins.  experimental results show that the algorithm converges quite rapidly and generates consensus structures that are visually similar to the input proteins. a comparison with other coordinate-based alignment algorithms shows that the proposed algorithm is competitive in terms of speed and the sizes of the conserved regions discovered in an extensive benchmark dataset derived from the homstrad and sabmark databases. the algorithm has been implemented in c++ and can be downloaded from the project's web page. alternatively, the algorithm can be used via a web server which makes it possible to align protein structures by uploading files from local disk or by downloading protein data from the rcsb protein data bank.  an algorithm is presented to compute a multiple structure alignment for a set of proteins, together with their consensus structure. experimental results show its effectiveness in terms of the quality of the alignment and computational cost. 