{"id":26999,"date":"2015-10-26T15:25:09","date_gmt":"2015-10-26T15:25:09","guid":{"rendered":"http:\/\/healthmedicinet.com\/news\/a-polynomial-time-algorithm-for-computing-the-area-under-a-gdt-curve\/"},"modified":"2015-10-26T15:25:09","modified_gmt":"2015-10-26T15:25:09","slug":"a-polynomial-time-algorithm-for-computing-the-area-under-a-gdt-curve","status":"publish","type":"post","link":"http:\/\/healthmedicinet.com\/news\/a-polynomial-time-algorithm-for-computing-the-area-under-a-gdt-curve\/","title":{"rendered":"A polynomial time algorithm for computing the area under a GDT curve"},"content":{"rendered":"<h4>Definition of the GDT function<\/h4>\n<p>The <em>GDT<\/em> function is a mapping that relates each distance cutoff <em>?<\/em> to the percentage of model residues that can be placed at distance ?<em>?<\/em> from the corresponding residues in the experimentally determined structure. The graph<br \/>\n         of a <em>GDT<\/em> function provides a valuable insight into the quality of a protein model (Fig.\u00c2\u00a01). More specifically, the closer the graph runs to the horizontal axis (in other words,<br \/>\n         the smaller the area under the graph), the better the model.<\/p>\n<p><strong>Fig.\u00c2\u00a01.<\/strong> CASP 8 example. <strong>a<\/strong><em>Red lines<\/em> represent <em>GDT<\/em> plots of different 3D models of the target protein T0482 submitted during the CASP8<br \/>\n         experiment. The model submitted by the group TS208 is represented in <em>blue<\/em>. <strong>b<\/strong> Structural alignment of the model submitted by the group TS208 (<em>blue<\/em>) and the experimental structure (<em>red<\/em>) over 67 residues evaluated by the CASP assessors\n      <\/p>\n<p>As a single numerical measure of the model quality, <em>GDT<\/em>_<em>TS<\/em> is extensively used at CASP to rank different models for the same target 13], 14]. Since it represents the average of <em>GDT<\/em>_<em>P <sub>?<\/sub><\/em><br \/>\n         at several distance cutoffs, <em>GDT<\/em>_<em>TS<\/em> is often viewed as an approximation of the area under the <em>GDT<\/em> curve (<em>GDT<\/em>_<em>A<\/em>) 10]\u00e2\u20ac\u201c12]:\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(1)<\/span><\/p>\n<p>However, as we demonstrate below, such a sparse sampling of the values of <em>GDT<\/em> function compromises the reliability of <em>GDT<\/em>_<em>TS<\/em>.\n      <\/p>\n<p>In our first example, we analyze the protein model for the target T0482, submitted<br \/>\n         by the group TS208 at CASP8 (Fig.\u00c2\u00a01). The <em>GDT<\/em>_<em>TS<\/em> score of this particular model was not even among the best dozen at CASP8, despite<br \/>\n         the fact that it fits the largest number of residues at distance <span class=\"inlinenumber\"><\/span> from the corresponding residues in the experimental structure. In fact, the blue<br \/>\n         model (Fig.\u00c2\u00a01a) can be superimposed onto the experimental structure so that all of its residues<br \/>\n         are at distance <span class=\"inlinenumber\"><\/span> from the residues in the experimental structure (Fig.\u00c2\u00a01b), while no such superposition exists for any other model, even for the distance<br \/>\n         cutoff of 10\u00c3\u2026. Interestingly, according to the MAMMOTH algorithm 15], the blue model is the best model for this particular target, while the DALI 16] algorithm ranks it as the second best.\n      <\/p>\n<p>Although it is impossible to tell whether #13 <em>GDT<\/em>_<em>TS<\/em> rank is more or less fair than #1 and #2 rank assigned by MAMMOTH and DALI, respectively,<br \/>\n         it is also not difficult to see that the ranking by the area under the <em>GDT<\/em> plot (<em>GDT<\/em>_<em>A<\/em>) would serve as a good compromise between these extremes.\n      <\/p>\n<p>The next two examples illustrate further disadvantages of <em>GDT<\/em>_<em>TS<\/em>. As seen in Fig.\u00c2\u00a02, better <em>GDT<\/em>_<em>TS<\/em> scores can be assigned to obviously worse models. Moreover, as demonstrated in Fig.\u00c2\u00a03, very similar models can have significantly different <em>GDT<\/em>_<em>TS<\/em> scores. <\/p>\n<p><strong>Fig.\u00c2\u00a02.<\/strong> Insensitivity of GDT_TS. This theoretical example shows no sensitivity of <em>GDT<\/em>_<em>TS<\/em> to large variations in model quality. Surprisingly, the <em>red model<\/em> has a better <em>GDT<\/em>_<em>TS<\/em> score than the better <em>blue model<\/em>, even though it is worse by all standards. Notice that, unlike <em>GDT<\/em>_<em>TS<\/em>, the <em>GDT<\/em>_<em>A<\/em> measure is not skewed by the values at the cutoff points 1, 2, 4 and 8\u00c2\u00a0\u00c3\u2026. In fact,<br \/>\n         the <em>GDT<\/em>_<em>A<\/em> score of the blue model is twice as good as that of the <em>red model<\/em><\/p>\n<p><strong>Fig.\u00c2\u00a03.<\/strong> Oversensitivity of GDT_TS. <strong>a<\/strong> A four helix bundle-like (toy) protein (<em>dashed grey line<\/em>) along with two of its, almost identical, models (<em>red<\/em> and <em>blue<\/em>). A realistic example of such a target protein (PDB ID: 1JM0A) is shown on the <em>right<\/em> (<strong>b<\/strong>). In this example, we assume that the protein and its models are extended to the<br \/>\n         right to include 100 or more residues. Note that, if <em>d<\/em>\u00c2\u00a0?\u00c2\u00a0{1\u00c2\u00a0\u00c3\u2026, 2\u00c2\u00a0\u00c3\u2026, 4\u00c2\u00a0\u00c3\u2026, 8\u00c2\u00a0\u00c3\u2026} then the <em>GDT<\/em> score of the <em>blue model<\/em> is significantly higher than that of the <em>red model<\/em>. For instance, if <em>d<\/em>\u00c2\u00a0=\u00c2\u00a02\u00c2\u00a0\u00c3\u2026, then the blue model has the <em>GDT_TS<\/em> score of about 87.5 since <strong>~<\/strong>50\u00c2\u00a0% all of its residues can be fit at distance ?1\u00c2\u00a0\u00c3\u2026 and 100\u00c2\u00a0% under each distance<br \/>\n         2, 4 and 8\u00c2\u00a0\u00c3\u2026 from the corresponding residues in the experimental structure (<em>dashed grey<\/em>). On the other hand, the <em>GDT_TS<\/em> score of the <em>red model<\/em> is only about 75, since only ~50\u00c2\u00a0% of the <em>red model\u00e2\u20ac\u2122s<\/em> residues can be placed under 1 and 2\u00c2\u00a0\u00c3\u2026 and 100\u00c2\u00a0% under 4 and 8\u00c2\u00a0\u00c3\u2026. In fact, no matter<br \/>\n         how close the <em>red model<\/em> gets to the <em>blue model<\/em>, its <em>GDT_TS<\/em> score will never improve. Note also that the <em>blue<\/em> and <em>red models<\/em> have almost identical <em>GDT_A<\/em> scores, since <em>GDT_A<\/em> is not sensitive to small coordinate changes\n      <\/p>\n<h4>Mathematical formalism<\/h4>\n<p>Strictly speaking, the <em>GDT<\/em> function is not well-defined. Zooming into the plot of the model highlighted in Fig.\u00c2\u00a01a, we see a set of many small vertical segments, meaning that each point on the horizontal<br \/>\n         axis is mapped to zero or more points on the vertical axis (Fig.\u00c2\u00a04). On the other hand, the inverse function (mapping each distance cutoffs <em>?<\/em> to the percentage of residues in the model structure that can be fit under the distance<br \/><em>?<\/em> from the corresponding residues in the experimental structure) is obviously well<br \/>\n         defined. This allows us to define the area under the <em>GDT<\/em> plot as the complement of the area under the inverse function:\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(2)<\/span><\/p>\n<p>where <em>Total<\/em>_<em>Area<\/em> represents the area of the rectangular region under consideration (100\u00c2\u00a0\u00c3\u2014\u00c2\u00a010). We<br \/>\n         start our mathematical formalism by first defining a protein structure.<\/p>\n<p><strong>Fig.\u00c2\u00a04.<\/strong> A closer look at the GDT_TS function. Zooming into the <em>GDT<\/em> plot of the model highlighted in Fig.\u00c2\u00a01. What appears to be the graph of a continuous function is, in fact, a set consisting<br \/>\n         of many separated <em>vertical line<\/em> segments\n      <\/p>\n<h4><strong>Definition 1<\/strong><\/h4>\n<p>A <em>protein structure a<\/em> is a sequence of points in the three dimensional Euclidean space <span class=\"inlinenumber\"><\/span><\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(3)<\/span><\/p>\n<p>The sequence elements <em>a <sub>i<\/sub><\/em><br \/>\n         can represent individual atoms, but it is more typical (in particular in protein structure<br \/>\n         prediction experiments) to assume that each point <em>a <sub>i<\/sub><\/em><br \/>\n         corresponds to the alpha-carbon atom of the protein\u00e2\u20ac\u2122s <em>ith<\/em> amino acid.\n      <\/p>\n<p>In what follows, we formally define the <em>GDT<\/em> function 17]. For simplicity of presentation, we will modify the codomain of <em>GDT<\/em> to represent the \u00e2\u20ac\u0153fraction of residues\u00e2\u20ac\u009d (ranging from 0 to 1) instead of \u00e2\u20ac\u0153percentages<br \/>\n         of residues\u00e2\u20ac\u009d (ranging from 0 to 100). We note that this simple rescaling of the ordinate<br \/>\n         values will have no effects on the results obtained in our study.\n      <\/p>\n<h4><strong>Definition 2<\/strong><\/h4>\n<p>Let <span class=\"inlinenumber\"><\/span> be a protein structure consisting of <em>n<\/em> amino acids, let <span class=\"inlinenumber\"><\/span> be a 3D model of <em>a<\/em>, and let <span class=\"inlinenumber\"><\/span> be a positive constant. The <em>Hubbard function (or GDT function)<\/em> is the function <span class=\"inlinenumber\"><\/span>, defined by <span class=\"inlinenumber\"><\/span>, where  denotes the Euclidean norm on <span class=\"inlinenumber\"><\/span> and <em>?<\/em> is a rigid transformation (a composition of a rotation and a translation).\n      <\/p>\n<h4><strong>Theorem 1<\/strong><\/h4>\n<p><em>H <sub>b<\/sub> is a stepwise function with finitely many steps<\/em><span class=\"inlinenumber\"><\/span>, 1\u00c2\u00a0?\u00c2\u00a0<em>k<\/em>\u00c2\u00a0?\u00c2\u00a0<em>n<\/em>\u00c2\u00a0?\u00c2\u00a01.\n      <\/p>\n<h4><em>Proof<\/em><\/h4>\n<p>Since <em>H <sub>b<\/sub><\/em><br \/>\n         is monotony non-decreasing and since the range of <em>H <sub>b<\/sub><\/em><br \/>\n         is a finite subset of (0,1], it follows that <em>H <sub>b<\/sub><\/em><br \/>\n         must be a stepwise function. To complete the proof, we note that the number of steps<br \/>\n         in <em>H <sub>b<\/sub><\/em><br \/>\n         matches the size of its range, which does not exceed <em>n<\/em>\u00c2\u00a0?\u00c2\u00a01, where <em>n<\/em> is the length of <em>b<\/em>.\n      <\/p>\n<p>For simplicity of presentation, from now on (and whenever the model <em>b<\/em> is implied), we will omit the subscript in <em>H <sub>b<\/sub><\/em><br \/>\n         and denote the Hubbard function only by <em>H<\/em>.\n      <\/p>\n<h4>Algorithm for GDT_A<\/h4>\n<p>The area under <em>H<\/em> is the sum of the areas of the rectangular regions (<em>? <sub>i<\/sub><\/em><br \/>\n         )(<em>? <sub>i<\/sub><\/em><br \/>\n         \u00c2\u00a0?\u00c2\u00a0<em>? <sub>i<\/sub><\/em><sub>?1<\/sub><br \/>\n         ):\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(4)<\/span><\/p>\n<p>where <em>?<\/em><sub>0<\/sub><br \/>\n         \u00c2\u00a0=\u00c2\u00a00 and <span class=\"inlinenumber\"><\/span> (Fig.\u00c2\u00a05). It would be trivial to compute <em>Area<\/em> had we known all <em>? <sub>i<\/sub><\/em><br \/>\n         and all function values <em>H<\/em>(<em>? <sub>i<\/sub><\/em><br \/>\n         ). Unfortunately, even if we knew the step points <em>? <sub>i<\/sub><\/em><br \/>\n         , it would be computationally very difficult to compute the function values at them,<br \/>\n         since the best to date algorithm for computing <em>H<\/em>(<em>? <sub>i<\/sub><\/em><br \/>\n         ) runs on the order of <em>O<\/em>(<em>n<\/em><sup>7<\/sup><br \/>\n         ) 7]. Hence, we resort to using the Riemann sums to approximate (instead of to compute<br \/>\n         exactly) the area under the graph of <em>H<\/em>.<\/p>\n<p><strong>Fig.\u00c2\u00a05.<\/strong> The general shape of the Hubbard function. Notice that the values <em>? <sub>i<\/sub><\/em><br \/>\n         along with the function values <em>H <sub>b<\/sub><\/em><br \/>\n         (<em>? <sub>i<\/sub><\/em><br \/>\n         ), <span class=\"inlinenumber\"><\/span>, uniquely determine the area under the graph of <em>H <sub>b<\/sub><\/em><br \/>\n         . At the biannual CASP experiment, <span class=\"inlinenumber\"><\/span><\/p>\n<p>The following definition and an accompanying theorem can be found in virtually any<br \/>\n         mathematical analysis textbook.\n      <\/p>\n<h4><strong>Definition 3<\/strong><\/h4>\n<p>If <span class=\"inlinenumber\"><\/span> is a function then <span class=\"inlinenumber\"><\/span> where <em>a<\/em>\u00c2\u00a0=\u00c2\u00a0<em>x<\/em><sub>0<\/sub><br \/>\n         \u00c2\u00a0\u00c2\u00a0<em>x<\/em><sub>1<\/sub><br \/>\n         \u00c2\u00a0\u00c2\u00a0\u00c2\u00b7\u00c2\u00b7\u00c2\u00b7\u00c2\u00a0\u00c2\u00a0<em>x <sub>n<\/sub><\/em><br \/>\n         \u00c2\u00a0=\u00c2\u00a0<em>b<\/em> is the partition of the interval [<em>a<\/em>,\u00c2\u00a0<em>b<\/em>] and <em>v <sub>i<\/sub><\/em><br \/>\n         denotes the supremum of <em>f<\/em> over [<em>x <sub>i<\/sub><\/em><sub>?1<\/sub><br \/>\n         ,\u00c2\u00a0<em>x <sub>i<\/sub><\/em><br \/>\n         ], is called the <em>upper Riemann sum<\/em> of <em>f<\/em> on [<em>a<\/em>,\u00c2\u00a0<em>b<\/em>].\n      <\/p>\n<h4><strong>Theorem 2<\/strong><\/h4>\n<p><em>Let f be a real, non-decreasing, Riemann integrable function on an interval<\/em> [<em>a<\/em>,\u00c2\u00a0<em>b<\/em>]. <em>Then<\/em><\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(5)<\/span><\/p>\n<p><em>where<\/em><\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(6)<\/span><\/p>\n<p><em>is the upper Riemann sum of f the and<\/em><span class=\"inlinenumber\"><\/span><\/p>\n<p>Observe that, since <em>H <sub>b<\/sub><\/em><br \/>\n         is piecewise continuous, it must be integrable on <span class=\"inlinenumber\"><\/span>. Thus, the area under the graph of <em>H<\/em> is\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(7)<\/span><\/p>\n<p>To approximate <em>Area<\/em> with a Riemann sum, one can define the partition points <span class=\"inlinenumber\"><\/span>, where <span class=\"inlinenumber\"><\/span> (Fig.\u00c2\u00a06) and then compute an estimate <em>Area<\/em>(<span class=\"inlinenumber\"><\/span>) of <em>Area<\/em> as\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(8)<\/span><\/p>\n<p><strong>Fig.\u00c2\u00a06.<\/strong> Approximation of the Hubbard function by the Riemann sum. <em>Area<\/em>(<span class=\"inlinenumber\"><\/span>) is the sum of the areas of all rectangular regions\n      <\/p>\n<p>The error |<em>Area<\/em>\u00c2\u00a0\u00e2\u20ac\u201c\u00c2\u00a0<em>Area<\/em> (<span class=\"inlinenumber\"><\/span>)| in the estimate (8) is below 2<span class=\"inlinenumber\"><\/span>. Up to a half of this error is due to the error in the Riemann sum with the remaining<br \/>\n         error being due to the possible placement of the last partition point <em>m<\/em><span class=\"inlinenumber\"><\/span> outside the interval <span class=\"inlinenumber\"><\/span>.\n      <\/p>\n<p>Unfortunately, computing the area estimates according to (8) is still a challenging problem, because (as we mentioned above), there is no computationally<br \/>\n         effective procedure for finding the function values <em>H<\/em>(<em>i<\/em><span class=\"inlinenumber\"><\/span>). To circumvent the problem, we utilize an efficient algorithm capable of computing<br \/>\n         the lower bound estimates <em>H <sub>i<\/sub><\/em><br \/>\n         of <em>H<\/em>(<em>i<\/em><span class=\"inlinenumber\"><\/span>), satisfying <span class=\"inlinenumber\"><\/span>, <span class=\"inlinenumber\"><\/span>. We then compute an estimate <span class=\"inlinenumber\"><\/span> of <em>Area<\/em> as\n      <\/p>\n<p class=\"inlinenumber\">\n<p class=\"inlinenumber\">\n<p><span>(9)<\/span><\/p>\n<p>Since <span class=\"inlinenumber\"><\/span>, it follows that <span class=\"inlinenumber\"><\/span> is a <span class=\"inlinenumber\"><\/span>-approximation of <em>Area<\/em>. Below we show how to compute all <em>H <sub>i<\/sub><\/em><br \/>\n         \u00e2\u20ac\u2122<em>s<\/em>, and, in turn, <span class=\"inlinenumber\"><\/span> in time <span class=\"inlinenumber\"><\/span>, where <em>n<\/em> is the length of <em>b<\/em>. Our algorithm takes advantage of an efficient procedure for computing near optimal<br \/><em>GDT<\/em>_<em>TS<\/em> values 5].\n      <\/p>\n<p>Let <em>T<\/em>(<em>b<\/em>) denotes the image of the model structure <em>b<\/em> under the transformation <em>T<\/em>. Denote by <span class=\"inlinenumber\"><\/span> the largest fraction of residues from <em>T<\/em>(<em>b<\/em>) that are at distance ?<em>?<\/em> from the corresponding residues in the experimental structure <em>a<\/em>. To find each <em>H <sub>i<\/sub><\/em><br \/>\n         , it is enough to compute a rigid body transformation <em>T <sub>i<\/sub><\/em><br \/>\n         satisfying <span class=\"inlinenumber\"><\/span>.\n      <\/p>\n<p>Denote by <em>T <sub>?<\/sub><\/em><br \/>\n         a transformation that places a largest subset <em>b <sub>?<\/sub><\/em><br \/>\n         of residues from <em>b<\/em> at distance ?<em>?<\/em> from the corresponding residues in the experimental structure. Given <em>T <sub>?<\/sub><\/em><br \/>\n         , one can easily compute <em>b <sub>?<\/sub><\/em><br \/>\n         by calculating all <em>n<\/em> distances between the residues <em>a <sub>i<\/sub><\/em><br \/>\n         and <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>i<\/sub><\/em><br \/>\n         ). Note that <em>P<\/em>(<em>T <sub>?<\/sub><\/em><br \/>\n         ,\u00c2\u00a0<em>?<\/em>)\u00c2\u00a0=\u00c2\u00a0<em>H<\/em>(<em>?<\/em>). We approximate the transformation <em>T <sub>?<\/sub><\/em><br \/>\n         by a so-called \u00e2\u20ac\u0153near-optimal\u00e2\u20ac\u009d transformation i.e., a transformation that places at<br \/>\n         least as many residues from the model structure under distance <span class=\"inlinenumber\"><\/span> as the optimal transformation <em>T <sub>?<\/sub><\/em><br \/>\n         places under the distance <em>?<\/em>. From now on, we will use <span class=\"inlinenumber\"><\/span> to denote a \u00e2\u20ac\u0153near-optimal\u00e2\u20ac\u009d transformation and the corresponding set of residues will<br \/>\n         be denoted by <span class=\"inlinenumber\"><\/span>. Observe that <span class=\"inlinenumber\"><\/span>.\n      <\/p>\n<p>Building upon any procedure for computing <span class=\"inlinenumber\"><\/span>, one can develop an algorithm for <span class=\"inlinenumber\"><\/span> by substituting <span class=\"inlinenumber\"><\/span> for <em>H <sub>i<\/sub><\/em><br \/>\n         in (10), where <span class=\"inlinenumber\"><\/span>. Several existing methods can be modified and made suitable for finding <span class=\"inlinenumber\"><\/span>. The most efficient such method relies on the concept of \u00e2\u20ac\u0153radial pair\u00e2\u20ac\u009d 5].\n      <\/p>\n<h4><strong>Definition 4<\/strong><\/h4>\n<p>Let <span class=\"inlinenumber\"><\/span> be a set of points in the three-dimensional Euclidean space. An ordered pair of points<br \/><span class=\"inlinenumber\"><\/span> is called a <em>radial pair<\/em> of <em>S<\/em> if <em>s <sub>j<\/sub><\/em><br \/>\n         is the furthest point from <em>s <sub>i<\/sub><\/em><br \/>\n         among all points in <em>S<\/em>.\n      <\/p>\n<h4><strong>Theorem 3<\/strong><\/h4>\n<p><em>Let T<\/em><sub>1<\/sub><em> and T<\/em><sub>2<\/sub><em>be two transformations and let<\/em><span class=\"inlinenumber\"><\/span><em> be a radial pair of S<\/em>. <em>If<\/em><span class=\"inlinenumber\"><\/span><em>and<\/em><span class=\"inlinenumber\"><\/span><em> then there exists a rotation R around the line through T<\/em><sub>1<\/sub><br \/>\n         (<em>s <sub>k<\/sub><\/em><br \/>\n         ) <em>and<\/em><span class=\"inlinenumber\"><\/span><em>such that<\/em><span class=\"inlinenumber\"><\/span>, <em>for any s <sub>p<\/sub>  in S<\/em>. <em>The rotation R can be found in time O<\/em> (<em>nlogn<\/em>), <em>where n is the size of S<\/em>.\n      <\/p>\n<p>A proof of the above theorem can be found in 5]. The algorithm for finding <em>R<\/em> is fairly straightforward and it relies on the so-called <em>plane<\/em>\u00e2\u20ac\u201c<em>sweep<\/em> approach 18].\n      <\/p>\n<p>The Theorem 3 implies that one choice for the near-optimal transformation <span class=\"inlinenumber\"><\/span> is the transformation <em>R<\/em>\u00c2\u00a0?\u00c2\u00a0<em>T<\/em>, where <em>T<\/em> is any transformation that maps the points <em>b <sub>k<\/sub><\/em><br \/>\n         and <em>b <sub>l<\/sub><\/em><br \/>\n         from the radial pair (<em>b <sub>k<\/sub><\/em><br \/>\n         ,\u00c2\u00a0<em>b <sub>l<\/sub><\/em><br \/>\n         ) of <em>b <sub>?<\/sub><\/em><br \/>\n         to the <span class=\"inlinenumber\"><\/span> neighborhoods of <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>k<\/sub><\/em><br \/>\n         ) and <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>l<\/sub><\/em><br \/>\n         ), respectively, and <em>R<\/em> is the rotation around the radial axis <span class=\"inlinenumber\"><\/span> that maps the remaining points from <em>T<\/em>(<em>b <sub>?<\/sub><\/em><br \/>\n         ) to the <span class=\"inlinenumber\"><\/span>-neighborhoods of the corresponding points from <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>?<\/sub><\/em><br \/>\n         ).\n      <\/p>\n<p>In search for a radial pair of <em>b <sub>?<\/sub><\/em><br \/>\n         , the algorithm in 5] explores all <em>n<\/em><sup>2<\/sup><br \/>\n         possible pairs of residues in <em>b<\/em>. For each candidate radial pair <span class=\"inlinenumber\"><\/span>, the algorithm generates a finite, representative set of transformations that map<br \/><em>b <sub>k<\/sub><\/em><br \/>\n         and <em>b <sub>l<\/sub><\/em><br \/>\n         into <span class=\"inlinenumber\"><\/span> neighborhoods of <em>a <sub>k<\/sub><\/em><br \/>\n         and <em>a <sub>l<\/sub><\/em><br \/>\n         , respectively (see the paragraph below for more details). For every such transformation<br \/><em>T<\/em>, a plane-sweep algorithm 18] is used to find a rotation <em>R<\/em> around the axis <span class=\"inlinenumber\"><\/span> that maximizes the number of residues from <em>R<\/em>(<em>T<\/em>(<em>b<\/em>)) that can be placed at distance <span class=\"inlinenumber\"><\/span> from the corresponding residues in <em>a<\/em>.\n      <\/p>\n<p>A finite set of transformations that map the residues <em>b <sub>k<\/sub><\/em><br \/>\n         and <em>b <sub>l<\/sub><\/em><br \/>\n         into the <span class=\"inlinenumber\"><\/span> neighborhoods of <em>a <sub>k<\/sub><\/em><br \/>\n         and <em>a <sub>l<\/sub><\/em><br \/>\n         , respectively, is constructed in such a way to ensure that for at least one of those<br \/>\n         transformation <em>T<\/em>, <span class=\"inlinenumber\"><\/span> and <span class=\"inlinenumber\"><\/span>. This can be achieved by partitioning <span class=\"inlinenumber\"><\/span> into small cubes of side length slightly smaller than <span class=\"inlinenumber\"><\/span> and then collecting the vertices of the cubes that are inside the open ball of radius<br \/><span class=\"inlinenumber\"><\/span> around <em>a <sub>k<\/sub><\/em><br \/>\n         (Fig.\u00c2\u00a07). The elements of this set, denoted by <em>A <sub>k<\/sub><\/em><br \/>\n         , are the candidate points <em>T<\/em>(<em>b <sub>k<\/sub><\/em><br \/>\n         ). The number of points in <em>A <sub>k<\/sub><\/em><br \/>\n         is <span class=\"inlinenumber\"><\/span> and at least one of them must be at distance <span class=\"inlinenumber\"><\/span> from <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>k<\/sub><\/em><br \/>\n         ) (Fig.\u00c2\u00a07). For each point <em>a <sup>k<\/sup><\/em><br \/>\n         \u00c2\u00a0?\u00c2\u00a0<em>A <sub>k<\/sub><\/em><br \/>\n         , the set <em>A <sub>l<\/sub><\/em><br \/>\n         (<em>a <sup>k<\/sup><\/em><br \/>\n         ) of possible images of <em>b <sub>l<\/sub><\/em><br \/>\n         under <em>T<\/em> is computed by discretizing the spherical cap <span class=\"inlinenumber\"><\/span>, where <em>S<\/em>(<em>a<\/em>,\u00c2\u00a0<em>r<\/em>) and <em>B<\/em>(<em>a<\/em>,\u00c2\u00a0<em>r<\/em>) denote the sphere and the open ball in <span class=\"inlinenumber\"><\/span> with center <em>a<\/em> and radius <em>r<\/em>, respectively, in such a way that at least one point from <em>A <sub>l<\/sub><\/em><br \/>\n         (<em>a <sup>k<\/sup><\/em><br \/>\n         ) is found at distance <span class=\"inlinenumber\"><\/span> from <em>T <sub>?<\/sub><\/em><br \/>\n         (<em>b <sub>l<\/sub><\/em><br \/>\n         ) (Fig.\u00c2\u00a07). We note that size of <em>A <sub>l<\/sub><\/em><br \/>\n         (<em>a <sup>k<\/sup><\/em><br \/>\n         ) is <span class=\"inlinenumber\"><\/span>. Hence, the total number of candidate pairs of points (<em>T<\/em>(<em>b <sub>k<\/sub><\/em><br \/>\n         ),\u00c2\u00a0<em>T<\/em>(<em>b <sub>l<\/sub><\/em><br \/>\n         )) is <span class=\"inlinenumber\"><\/span>.<\/p>\n<p><strong>Fig.\u00c2\u00a07.<\/strong> Discretizing the space of rigid body transformations. 2D illustration of <em>A <sub>k<\/sub><\/em><br \/>\n         (the set of the vertices of the <em>squares<\/em> shown on the <em>left<\/em>) and the set <em>A <sub>l<\/sub><\/em><br \/>\n         (<em>a <sup>k<\/sup><\/em><br \/>\n         ) generated for one <em>a <sub>k<\/sub><\/em><br \/>\n         \u00c2\u00a0?\u00c2\u00a0<em>A <sub>k<\/sub><\/em><\/p>\n<p>An obvious to compute <span class=\"inlinenumber\"><\/span> is to run the just described algorithm <em>m<\/em> times in succession, for <span class=\"inlinenumber\"><\/span>. However, such an approach results in many unnecessary repeated calculations as the<br \/>\n         area around <em>a <sub>k<\/sub><\/em><br \/>\n         and the corresponding spherical cap in the neighborhoods of <em>a <sub>l<\/sub><\/em><br \/>\n         are discretized over and over again. Moreover, all transformations <em>T<\/em> and <em>R<\/em>, generated and inspected during the procedure for finding <span class=\"inlinenumber\"><\/span>, are inspected again during the procedure for finding <span class=\"inlinenumber\"><\/span>, for each <em>j<\/em>\u00c2\u00a0\u00c2\u00a0<em>i<\/em>. <\/p>\n<p>We show that all transformations <span class=\"inlinenumber\"><\/span> and the corresponding values <em>H<\/em><sub>1<\/sub><br \/>\n         ,\u00c2\u00a0\u00e2\u20ac\u00a6,\u00c2\u00a0<em>H <sub>m<\/sub><\/em><br \/>\n         can be computed, at once, during the procedure of finding the last transformation,<br \/>\n         namely <span class=\"inlinenumber\"><\/span>. As demonstrated in the pseudocode above, the transformation <em>T<\/em> is generated only once for each pair of points <span class=\"inlinenumber\"><\/span> and a sweep-plane algorithm for finding <em>R<\/em> is called only once for each <em>i<\/em> satisfying <span class=\"inlinenumber\"><\/span> and <span class=\"inlinenumber\"><\/span>. The values of <em>H <sub>i<\/sub><\/em><br \/>\n         are updated on the fly.\n      <\/p>\n<h4>Running time analysis<\/h4>\n<p>To analyze the algorithm\u00e2\u20ac\u2122s running time, we note that the number of iterations of<br \/>\n         the first<em> for<\/em> loop is equal to the number of candidate radial pairs (<em>b <sub>k<\/sub><\/em><br \/>\n         ,\u00c2\u00a0<em>b <sub>l<\/sub><\/em><br \/>\n         ), which is <span class=\"inlinenumber\"><\/span> The number of iterations of the second <em>for<\/em> loop matches the number of pairs of grid points around <em>a <sup>k<\/sup><\/em><br \/>\n         and <em>a <sup>l<\/sup><\/em><br \/>\n         , which is <span class=\"inlinenumber\"><\/span>. Each one of <span class=\"inlinenumber\"><\/span> iterations of the third <em>for<\/em> loop calls a <em>O<\/em>(<em>nlogn<\/em>) plane-sweep procedure to compute an optimal rotation and (if needed) to update the<br \/>\n         value <em>H <sub>i<\/sub><\/em><br \/>\n         . Hence, the asymptotic time complexity of the three nested <em>for<\/em> loops is <span class=\"inlinenumber\"><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Definition of the GDT function The GDT function is a mapping that relates each distance cutoff ? to the percentage of model residues that can be placed at distance ?? from the corresponding residues in the experimentally determined structure. The graph of a GDT function provides a valuable insight into the quality of a protein [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-26999","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/posts\/26999","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/comments?post=26999"}],"version-history":[{"count":0,"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/posts\/26999\/revisions"}],"wp:attachment":[{"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/media?parent=26999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/categories?post=26999"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/healthmedicinet.com\/news\/wp-json\/wp\/v2\/tags?post=26999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}