Tree algorithm pdf

The prediction accuracy of one amino acid is the ratio of the number of correctly predicted residues to the number of all the residues with this amino acid type. Table I lists the prediction accuracy of 18 types of amino acids. Each amino acid has one to four torsion angles depending on its type.

Given a residue with known backbone coordinates, if its torsion angles are known, then the coordinates of its side-chain atom can be uniquely determined.

If the distance between two rotamer atoms is no more than the sum of their radii, then there is an interaction between the two residues to which these two rotamers belong.

To tell if there is an interaction between two residues or not, we need to consider the following three factors: the spatial positions of the backbones of the two residues, the size of their rotamers and the orientation of their rotamers. In fact, it is possi- ble that two residues e. Some amino acids have only one torsion angle.

The running time of TreePack depends on the atom radii used in TreePack. When tested on the proteins, there is no obvious difference in terms of the running time since TreePack runs really fast on these test proteins.

The prediction accuracy also depends on the atom radii. TreePack uses VDW radii as the default to achieve a good prediction accuracy without losing too much computational efficiency. We tested our program TreePack on nonnative backbones generated by a protein threading program. We arbitrarily chose 24 CASP6 test proteins3 and then used a protein threading server RAPTOR to find their best templates and to generate the alignments between the test proteins and their templates.

Most of the test proteins have a good alignment to their best templates. SCAP runs very slowly compared to the other three programs. Table V gives the overall prediction accuracy of the four programs.

This result indicates that TreePack also works well for the nonnative backbones. Theoretical Results 6. The side-chain packing problem is still NP-hard even if a protein structure is modeled by a geometric neighborhood graph.

A protein with n L residues. Each grid point corresponds to a residue. Therefore, it is necessary to provide a new hardness proof for our model since a residue interaction graph provides more information than a general graph. Here, we prove the following two hardness results, assuming that there is no interaction between two residues if their distance is beyond a constant Du. However, we do not specify the singleton and pairwise interaction scores.

Protein side-chain packing is NP-hard even if all the energy items are negative or zero. We reduce the longest common subsequence problem to this problem. The longest common subsequence problem is defined as follows. Given any n strings s1 , s2 ,. For a detailed description and hardness proof of the longest common subsequence problem, please refer to Jiang and Li [].

Here we use si l to denote the lth character of string si. As shown in Figure 5, we construct a protein structure in a 2D grid of length n and width L. Assume there is an interaction edge between two residues if and only if their distance in the grid is 1.

Let c R denote the character type of rotamer R. This condition maintains the order of the characters in a string. There is a common subsequence of length L among s1 , s2 ,.

On one hand, if there is a common subsequence of length L, then for the residue at grid point i, j , we choose the rotamer Ri,l j identified by si l j and l j , where l j is the position of the jth common subsequence character in string si. So the side-chain assignment implies a common subsequence of at least L. Since the longest common subsequence problem is NP-hard, this argument completes the proof.

Protein side-chain packing is NP-hard even if all energy items are nonnegative. This theorem can be proved using a technique similar to the proof of Theorem 6. However, the following scoring function is used.

Otherwise, their pairwise score is 1. Using a similar analysis in the proof of Theorem 6. We introduce several polynomial-time approximation schemes PTAS for the side-chain packing prob- lem, each scheme suitable for a different type of energy function, some of which make sense in practice. In contrast, using a general graph model of protein struc- tures, one group [Chazelle et al. The basic idea underlying these algorithms is to partition the whole protein struc- ture into small blocks, assign side chains to each block separately, and then combine the assignments of all the blocks.

We assume that the protein under consideration is inscribed in a minimal 3D rectangle with dimensions Wx , W y , and Wz and the left bottom corner of the rectangle is the origin point. LEMMA 6. If every energy item in Eq. For simplicity, in this proof, we assume that we want to maximize Eq.

The intuition is to cut the protein structure into some nonoverlapping blocks using k different partitioning schemes. Each block can be tree-decomposed into some components containing no more than O kWx residues.

Therefore, the side-chain packing of each block can be done within time O kWx proportional to O n rot , using the globally optimal algorithm on each block. We then prove that among k different partitioning schemes, at least one can give us a good side-chain packing. We optimize the side-chain assignment for the residues in RSs first using our tree-decomposition-based algorithm and then for the remaining residues that is, the residues in the white area while fixing the side-chain assignment to the residues in RSs.

The union of RSs and BSs contains all the residues and inter-residue interaction edges in the protein. Since all the energy items are non-negative, the total energy E s is greater W Wy If the subscript of B is greater than Duy , then we replace the subscript with its module over 5 Du.

For each partition scheme, we do side-chain assignment for all the residues in the shadowed areas first and then for the remaining residues. For each partition scheme s, the algorithm needs to optimize the side-chain assignment for the residues in RSs. Based on Lemma 3. So the time O kWx complexity of doing side-chain packing for each partition scheme is O Nnrot O kWx and the time complexity of this algorithm is O kNnrot.

Lemma 6. We can further cut the protein along the x-axis to obtain the following desired theorem. The detailed proof of the above theorem is shown in the Appendix. Instead, we have the following theorem.

Assume that all the pairwise energy items in Eq. The detailed proof of Theorem 6. If all the pairwise scores are negative, then using a technique similar to the proof of Theorem 6.

Assume that all the pairwise scores in Eq. Theorems 6. That is, we can have a good approximation algorithm if there is no way to avoid all the atomic clashes in the whole system. This condition usually holds if the protein backbone is predicted by a protein threading technique or if there are heavy potential atomic clashes in the system.

Conclusions We presented a tree-decomposition-based algorithm, TreePack, for protein side- chain prediction. Using the tree decomposition of protein structures, we not only give a fast, rigorous and ac- curate protein side-chain assignment method, but also develop several polynomial- time approximation schemes PTAS for this problem. These theoretical results also open up a new avenue of study for the side-chain packing problem. On one hand, they stimulate us to develop a physically meaningful energy function so that the PTAS algorithms can be used to approximate the system energy to an arbitrary precision.

On the other hand, we could further enlarge the rotamer library to take advantage of the computational efficiency of our algorithms, which should in turn give better prediction accuracy. We are currently pursuing combining the tree decomposition technique and the protein structure partition technique used in the PTAS algorithm to develop a heuris- tic algorithm for the side-chain packing problem with any kind of energy function.

That is, if the tree width of the whole residue interaction graph is big, then we first cut the protein structure into several small blocks such that each small block has a reasonable tree width. Then we use the tree-decomposition-based algorithm to do side-chain assignment for each small block separately.

Using various partition schemes, this heuristic algorithm should be able to generate a reasonable side-chain packing for the whole protein structure. Appendix A. Figure 8 gives an exam- ple of the algorithm described in the proof of Theorem 3. Please note that the tree decomposition generated by this algorithm might not have the optimal treewidth. For simplicity, we assume that we want to maximize Eq. The proof of this theorem is very similar to that of Lemma 6.

In accordance with Lemma 6. Similarly, We can also prove that the sum of the energies of all the subgraphs Ti is no more than 2E opt. The time complexity O k 2 is k 2 Nnrot.

We use a slightly different partition method to cut the protein structure into small blocks. An illustration of tree decomposition process using the minimum-degree heuristic technique. This technique employs the following procedures: i choose the vertex with the minimal degree. The chosen vertex and its neighbors form a component; ii make the neighbors of the chosen vertex form a clique; iii remove the chosen vertex and repeat the above two steps on the remaining subgraph until the subgraph is empty.

We optimize the side-chain assignment for the protein structure using k 2 different partition schemes and prove that at least one of them will give a good side-chain packing. Obviously, any two Ri1 , j1 , Ri2 , j2 in RSr,c are disjoint.

An illustration of tree decomposition process using the algorithm presented in the proof of Theorem 3. All the separators on the path from Si to S1 form a decomposition component. The height of the tree is O log V. We assign side chains to all the residues in the protein structure by optimizing the energy of each subsystem induced by an individual R in RSr,c independently. Let E Rr,c denote the optimal energy of the subsystem Rr,c and let E Cr,c denote the energy of Cr,c given that the side-chain assignment to all the residues in RSr,c are already fixed.

We have the following equation. We are grateful to Dr. Julio Kovacs, who tried out TreePack and gave us helpful comments and test instances. The authors would like to thank all the anonymous reviewers, whose insightful comments are very helpful to the improvement of the article. NP-hardness results for protein side-chain packing. In Genome Informatics 8, S. Miyano and T.

Takagi, Eds. Fast protein fold recognition via sequence to structure alignment and contact capacity potentials. In Biocomputing: Proceedings of Pacific Symposium. AMIR, E. Efficient approximation for triangulation of minimum treewdith. Complexity of finding embedding in a k-tree.

SIAM J. ARYA, S. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. ACM 45, — BACH, F. Thin junction trees. Dietterich, S. Becker, and Z. Ghahramani, Eds. The minimum degree heuristic and the minimal triangulation process. In Lecture Notes in Computer Science, vol.

Springer-Verlag, New York, 58— Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A new homology modeling tool. A graph-theory algorithm for rapid protein side-chain prediction. A semidefinite programming approach to side- chain positioning with new rounding strategies.

Follow the same algorithm for each node. To know about the implementation of binary search tree data structure, please click here. Ravi Kiran. Arnab Chakraborty. Parth Panjabi. Eduonix Learning Solutions. Data Structure and Algorithms - Tree Advertisements. Previous Page. Next Page. Useful Video Courses. Thus this method improves algorithms to generate minimum spanning tree of a graph. Introduction A minimum spanning tree of an undirected weighted graph can be easily obtained using classical algorithms by Prim or Kruskal.

A number of algorithms have been proposed to enumerate all spanning trees of an undirected graph [2,5]. At first we remind briefly some definitions in graph theory and algorithms have made previous for M ST. The weight of an edge is often called its cost or distance. A tree is a subgraph of G that does not contain any cycle. As a result, there is exactly one path from each vertex to another vertex in a tree. A spanning tree T of a connected weighted graph G is a tree containing all vertices of G.

Every connected graph has a spanning tree. A minimum spanning tree M ST of an undirected weighted graph G is a spanning tree of which the sum of the edge weights costs is minimal [1,3]. The Minimum Spanning Tree Problem Several algorithms exist for generating all spanning trees of a graph [4,5], also elementary graph algorithms, Breadth-first and Depth-first search.

Good space and time complexities are the most important concerns of these algorithms. Most algorithms generate spanning trees using some fundamental cut or circuit, but none of them takes the cost of the tree into account while generating spanning trees.

Date: July 1, and, in revised form, July 30, Primary 05C85, 68W Key words and phrases. Graph theory, weighted spanning trees, minimum spanning tree, min- imum spanning tree algorithms. Process of algorithm step by step. There are several greedy algorithms for finding a minimal spanning tree of a graph. In these algorithms we start from a vertex , the initial node, and after process by selecting many vertexes according algorithm, obtain a spanning tree with minimum cost [2].

Many algorithms are single source shortest path problem. Some algorithm needed for sorting all the edges in graph. Therefore it do this by building a priority queue of edges in linear time. Another obtain random graphs with random edge weights and find low cost, and it may the M ST was not complete practically. In special cases these algorithms have O E. Description of the algorithm Let G is a connected, edge-weighted graph.