@Article{Senior2020, author = {Andrew W. Senior and Richard Evans and John Jumper and James Kirkpatrick and Laurent Sifre and Tim Green and Chongli Qin and Augustin {\v{Z}}{\'{\i}}dek and Alexander W. R. Nelson and Alex Bridgland and Hugo Penedones and Stig Petersen and Karen Simonyan and Steve Crossan and Pushmeet Kohli and David T. Jones and David Silver and Koray Kavukcuoglu and Demis Hassabis}, journal = {Nature}, title = {Improved protein structure prediction using potentials from deep learning}, year = {2020}, month = {jan}, number = {7792}, pages = {706--710}, volume = {577}, doi = {10.1038/s41586-019-1923-7}, file = {:by-author/S/Senior/2020_Senior_706.pdf:PDF}, keywords = {CS, AlphaFold, bioinformatics, protein folding, machine learning, ANN, artificial neural networks}, owner = {saulius}, publisher = {Springer Science and Business Media {LLC}}, timestamp = {2021.01.08}, } @Article{Arun1987, author = {Arun, K. S. and Huang, T. S. and Blostein, S. D.}, journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on}, title = {Least-Squares Fitting of Two 3-D Point Sets}, year = {1987}, issn = {0162-8828}, pages = {698 -700}, volume = {PAMI-9}, abstract = {Two point sets {pi} and {p'i}; i = 1, 2,..., N are related by p'i = Rpi + T + Ni, where R is a rotation matrix, T a translation vector, and Ni a noise vector. Given {pi} and {p'i}, we present an algorithm for finding the least-squares solution of R and T, which is based on the singular value decomposition (SVD) of a 3 × 3 matrix. This new algorithm is compared to two earlier algorithms with respect to computer time requirements.}, doi = {10.1109/TPAMI.1987.4767965}, file = {1987_Arun_698.pdf:by-author/A/Arun/1987_Arun_698.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {algorithms, structure superposition}, owner = {saulius}, timestamp = {2012.05.16}, } @Article{Arya1998, author = {Arya, Sunil and Mount, David M. and Netanyahu, Nathan S. and Silverman, Ruth and Wu, Angela Y.}, journal = {J. ACM}, title = {An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions}, year = {1998}, issn = {0004-5411}, pages = {891--923}, volume = {45}, doi = {10.1145/293347.293348}, file = {:by-author/A/Arya/1998_Arya_891.pdf:PDF}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://doi.acm.org/10.1145/293347.293348}, } @Manual{Baudin2010, title = {{N}elder-{M}ead User’s Manual}, author = {Baudin}, year = {2010}, abstract = {In this document, we present the Nelder-Mead component provided in Scilab. The introduction gives a brief overview of the optimization features of the component and present an introductory example. Then we present some theory associated with the simplex, a geometric concept which is central in the Nelder-Mead algorithm. We present several method to compute an initial simplex. Then we present Spendley’s et al. fixed shape unconstrained optimization algorithm. Several numerical experiments are provided, which shows how this algorithm performs on well-scaled and badly scaled quadratics. In the final section, we present the Nelder-Mead variable shape unconstrained optimization algorithm. Several numerical experiments are presented, where some of these are counter examples, that is cases where the algorithms fails to converge on a stationnary point. In the appendix of this document, the interested reader will find a bibliography of simplex-based algorithms, along with an analysis of the various implementations which are available in several programming languages.}, file = {:by-author/B/Baudin/2010_Baudin.pdf:PDF}, keywords = {CS,minimisation,simplex method}, owner = {saulius}, timestamp = {2012.10.21}, } @Article{Bedem2009, author = {van den Bedem, Henry and Dhanik, Ankur and Latombe, Jean-Claude and Deacon, Ashley M.}, journal = {Acta Crystallographica Section D}, title = {Modeling discrete heterogeneity in X-ray diffraction data by fitting multi-conformers}, year = {2009}, pages = {1107--1117}, volume = {65}, abstract = {The native state of a protein is regarded to be an ensemble of conformers, which allows association with binding partners. While some of this structural heterogeneity is retained upon crystallization, reliably extracting heterogeneous features from diffraction data has remained a challenge. In this study, a new algorithm for the automatic modelling of discrete heterogeneity is presented. At high resolution, the authors' single multi-conformer model, with correlated structural features to represent heterogeneity, shows improved agreement with the diffraction data compared with a single-conformer model. The model appears to be representative of the set of structures present in the crystal. In contrast, below 2 Å resolution representing ambiguous electron density by correlated multi-conformers in a single model does not yield better agreement with the experimental data. Consistent with previous studies, this suggests that variability in multi-conformer models at lower resolution levels reflects uncertainty more than coordinated motion.}, doi = {10.1107/S0907444909030613}, file = {2009_Bedem_1107.pdf:by-author/B/Bedem/2009_Bedem_1107.pdf:PDF}, keywords = {protein crystallography, xray crystallography, algorithms, structure refinement, heterogeneity, modeling, multi-conformers}, owner = {saulius}, timestamp = {2013.03.25}, url = {http://dx.doi.org/10.1107/S0907444909030613}, } @Article{Beichl2000, author = {Beichl, I. and Sullivan, F.}, journal = {Computing in Science \& Engineering}, title = {The Metropolis Algorithm}, year = {2000}, month = {Feb}, note = {ISSN: 1521-9615 References Cited: 6 Cited by : 14 INSPEC Accession Number: 6463882 Date of Current Version: 06 August 2002}, number = {1}, pages = {65--69}, volume = {2}, abstract = {The Metropolis Algorithm has been the most successful and influential of all the members of the computational species that used to be called the "Monte Carlo method". Today, topics related to this algorithm constitute an entire field of computational science supported by a deep theory and having applications ranging from physical simulations to the foundations of computational complexity. Since the rejection method invention (J. von Neumann), it has been developed extensively and applied in a wide variety of settings. The Metropolis Algorithm can be formulated as an instance of the rejection method used for generating steps in a Markov chain}, doi = {10.1109/5992.814660}, file = {2000_Beichl_65.pdf:by-author/B/Beichl/2000_Beichl_65.pdf:PDF}, groups = {sg/Molecular dynamics}, keywords = {molecular dynamics,Monte Carlo}, owner = {saulius}, timestamp = {2011.10.21}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=814660&tag=1}, } @Article{Bourgeois1971, author = {Bourgeois, Fran\c{c}ois and Lassalle, Jean-Claude}, journal = {Commun. ACM}, title = {An extension of the Munkres algorithm for the assignment problem to rectangular matrices}, year = {1971}, issn = {0001-0782}, pages = {802--804}, volume = {14}, acmid = {362945}, address = {New York, NY, USA}, doi = {10.1145/362919.362945}, file = {:by-author/B/Bourgeois/1971_Bourgeois_802.pdf:PDF}, issue_date = {Dec. 1971}, keywords = {algorithms, assignment problem, operations research, optimization theory, rectangular matrices}, numpages = {3}, owner = {saulius}, publisher = {ACM}, timestamp = {2012.04.05}, url = {http://doi.acm.org/10.1145/362919.362945}, } @Article{Chen2004, author = {Chen, Chuanbo and Li, Qishen}, journal = {Acta Crystallographica Section A}, title = {A strict solution for the optimal superimposition of protein structures}, year = {2004}, pages = {201--203}, volume = {60}, abstract = {Existing methods for the optimal superimposition of one vector set on another in the comparison of parts or the whole of related protein molecules are based on the precondition that the centroids of the two sets are coincident. As a result, the translation components of the transformation are artificially removed from the superimposition process. This is obviously not strict in the mathematical sense. The theorem presented in this paper is a strict solution for the optimal superimposition of two vector sets, which is in fact the problem of the weighted optimal rigid superimposition of two vector sets. Examples show its advantages compared with the method of simply coinciding the centroids of the two vector sets for the translation transformation.}, doi = {10.1107/S0108767304003654}, file = {2004_Chen_201.pdf:by-author/C/Chen/2004_Chen_201.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition, algorithms}, owner = {saulius}, timestamp = {2012.05.16}, url = {http://dx.doi.org/10.1107/S0108767304003654}, } @Article{Christopher1996, author = {Christopher, J. A. and Swanson, R. and Baldwin, T. O.}, journal = {Computers \& chemistry}, title = {Algorithms for finding the axis of a helix: fast rotational and parametric least-squares methods.}, year = {1996}, pages = {339--45}, volume = {20}, abstract = {Several methods for finding the axis of a helix are presented and compared. The most accurate determines the helix axis as the axis of rotation necessary to map point i to point i + 1 of the helix. The fastest method calculates the helix axis as the best-fit line through the coordinates by a three-dimensional parametric linear least-squares algorithm, taking advantage of the sequential nature of the data.}, file = {:by-author/C/Christopher/1996_Christopher_339.pdf:PDF}, keywords = {protein bioinformatics, helical parameters}, owner = {saulius}, timestamp = {2012.10.21}, } @Article{Chung1999, author = {Chung, S. Y. and Subbiah, S.}, journal = {Proteins}, title = {Validation of NMR side-chain conformations by packing calculations.}, year = {1999}, pages = {184--94}, volume = {35}, abstract = {The precision and accuracy of protein structures determined by nuclear magnetic resonance (NMR) spectroscopy depend on the completeness of input experimental data set. Typically, rather than a single structure, an ensemble of up to 20 equally representative conformers is generated and routinely deposited in the Protein Database. There are substantially more experimentally derived restraints available to define the main-chain coordinates than those of the side chains. Consequently, the side-chain conformations among the conformers are more variable and less well defined than those of the backbone. Even when a side chain is determined with high precision and is found to adopt very similar orientations among all the conformers in the ensemble, it is possible that its orientation might still be incorrect. Thus, it would be helpful if there were a method to assess independently the side-chain orientations determined by NMR. Recently, homology modeling by side-chain packing algorithms has been shown to be successful in predicting the side-chain conformations of the buried residues for a protein when the main-chain coordinates and sequence information are given. Since the main-chain coordinates determined by NMR are consistently more reliable than those of the side-chains, we have applied the side-chain packing algorithms to predict side-chain conformations that are compatible with the NMR-derived backbone. Using four test cases where the NMR solution structures and the X-ray crystal structure of the same protein are available, we demonstrate that the side-chain packing method can provide independent validation for the side-chain conformations of NMR structures. Comparison of the side-chain conformations derived by side-chain packing prediction and by NMR spectroscopy demonstrates that when there is agreement between the NMR model and the predicted model, on average 78% of the time the X-ray structure also concurs. While the side-chain packing method can confirm the reliable residue conformations in NMR models, more importantly, it can also identify the questionable residue conformations with an accuracy of 60%. This validation method can serve to increase the confidence level for potential users of structural models determined by NMR.}, file = {:by-author/C/Chung/1999_Chung_184.pdf:PDF}, keywords = {protein bioinformatics, quality estimation}, owner = {saulius}, timestamp = {2012.10.21}, } @InProceedings{Ciaccia1997, author = {Ciaccia, Paolo and Patella, Marco and Zezula, Pavel}, booktitle = {Proceedings of the 23rd International Conference on Very Large Data Bases}, title = {M-tree: An Efficient Access Method for Similarity Search in Metric Spaces}, year = {1997}, address = {San Francisco, CA, USA}, pages = {426--435}, publisher = {Morgan Kaufmann Publishers Inc.}, series = {VLDB '97}, abstract = {A new access method, called M-tree, is proposed to organize and search large data sets from a generic "metric space", i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the M-tree always balanced - several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and k-nearest neighbors) queries are also described. Results from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O's and the number of distance computations. The results demonstrate that the M-tree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files.}, file = {:by-author/C/Ciaccia/1997_Ciaccia_426.pdf:PDF}, isbn = {1-55860-470-7}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://dl.acm.org/citation.cfm?id=645923.671005}, } @Article{Cieplak2001, author = {T. Cieplak and J.L. Wisniewski}, journal = {Molecules}, title = {A New Effective Algorithm for the Unambiguous Identification of the Stereochemical Characteristics of Compounds During Their Registration in Databases}, year = {2001}, pages = {915--926}, volume = {6}, abstract = {A new effective algorithm for handling of geometry at chiral centers for the processing of stereochemical structures during their unambiguous registration in databases was designed, programmed and implemented. The chemical and mathematical reasoning behind the algorithm are discussed in detail. Its advantages- in comparison to the methods used so far - are illustrated for the manual as well as for the computer- assisted assignment of stereodescriptors based on the CIP ranking procedure.}, doi = {10.3390/61100915}, file = {:by-author/C/Cieplak/2001_Cieplak_915.pdf:PDF}, keywords = {Stereochemistry, CIP, Stereodescriptors. Determinant algorithm, Chirality}, owner = {saulius}, timestamp = {2014.01.26}, url = {http://www.mdpi.com/1420-3049/6/11/915}, } @Article{Coutsias2004, author = {Coutsias, Evangelos A. and Seok, Chaok and Dill, Ken A.}, journal = {Journal of Computational Chemistry}, title = {Using quaternions to calculate {RMSD}}, year = {2004}, pages = {1849--1857}, volume = {25}, abstract = {A widely used way to compare the structures of biomolecules or solid bodies is to translate and rotate one structure with respect to the other to minimize the root-mean-square deviation (RMSD). We present a simple derivation, based on quaternions, for the optimal solid body transformation (rotation-translation) that minimizes the RMSD between two sets of vectors. We prove that the quaternion method is equivalent to the well-known formula due to Kabsch. We analyze the various cases that may arise, and give a complete enumeration of the special cases in terms of the arrangement of the eigenvalues of a traceless, 4 x 4 symmetric matrix. A key result here is an expression for the gradient of the RMSD as a function of model parameters. This can be useful, for example, in finding the minimum energy path of a reaction using the elastic band methods or in optimizing model parameters to best fit a target structure.}, doi = {10.1002/jcc.20110}, file = {:by-author/C/Coutsias/2004_Coutsias_1849.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {xray crystallography, algorithms, structure superposition, quaternions}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://dx.doi.org/10.1002/jcc.20110}, } @Article{Damm2006, author = {Damm, Kelly L. and Carlson, Heather A.}, journal = {Biophysical journal}, title = {Gaussian-weighted RMSD superposition of proteins: a structural comparison for flexible proteins and predicted protein structures.}, year = {2006}, pages = {4558--73}, volume = {90}, abstract = {Many proteins contain flexible structures such as loops and hinged domains. A simple root mean square deviation (RMSD) alignment of two different conformations of the same protein can be skewed by the difference between the mobile regions. To overcome this problem, we have developed a novel method to overlay two protein conformations by their atomic coordinates using a Gaussian-weighted RMSD (wRMSD) fit. The algorithm is based on the Kabsch least-squares method and determines an optimal transformation between two molecules by calculating the minimal weighted deviation between the two coordinate sets. Unlike other techniques that choose subsets of residues to overlay, all atoms are included in the wRMSD overlay. Atoms that barely move between the two conformations will have a greater weighting than those that have a large displacement. Our superposition tool has produced successful alignments when applied to proteins for which two conformations are known. The transformation calculation is heavily weighted by the coordinates of the static region of the two conformations, highlighting the range of flexibility in the overlaid structures. Lastly, we show how wRMSD fits can be used to evaluate predicted protein structures. Comparing a predicted fold to its experimentally determined target structure is another case of comparing two protein conformations of the same sequence, and the degree of alignment directly reflects the quality of the prediction.}, doi = {10.1529/biophysj.105.066654}, file = {:by-author/D/Damm/2006_Damm_4558.pdf:PDF;manuscript:by-author/D/Damm/2006_Damm_4558_manuscript.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{Diamond1988, author = {Diamond, R.}, journal = {Acta Crystallographica Section A}, title = {A note on the rotational superposition problem}, year = {1988}, pages = {211--216}, volume = {44}, doi = {10.1107/S0108767387010535}, file = {1988_Diamond_211.pdf:by-author/D/Diamond/1988_Diamond_211.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {algorithms, structure superposition, xray crystallography}, owner = {saulius}, timestamp = {2012.05.15}, url = {http://dx.doi.org/10.1107/S0108767387010535}, } @Article{Diamond1976, author = {R. Diamond}, journal = {Acta Crystallographica Section A}, title = {On the comparison of conformations using linear and quadratic transformations}, year = {1976}, pages = {1--10}, volume = {32}, abstract = {A means is developed whereby coordinate sets for related molecules may be compared in such a way as to express rigorously the relationship between them in terms of position, orientation, homogeneous strain and curvature. It is thought that such curvatures may be of value in characterizing hinge regions of allosteric enzymes. The method is illustrated with examples taken from haemoglobin and myoglobin}, doi = {10.1107/S0567739476000016}, file = {:by-author/D/Diamond/1976_Diamond_1.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {xray crystallography, algorithms, structure superposition}, owner = {saulius}, timestamp = {2008.07.28}, } @Article{Dong2002, author = {Qunfeng Dong and Zhijun Wu}, journal = {Journal of Global Optimization}, title = {A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances}, year = {2002}, pages = {365--375}, volume = {22}, abstract = {We describe a linear-time algorithm for solving the molecular distance geometry problem with exact distances between all pairs of atoms. This problem needs to be solved in every iteration of general distance geometry algorithms for protein modeling such as the EMBED algorithm by Crippen and Havel (Distance Geometry and Molecular Conformation, Wiley, 1988). However, previous approaches to the problem rely on decomposing an distance matrix or minimizing an error function and require $O(n^2)$ to $O(n^3)$ floating point operations. The linear-time algorithm will provide a much more efficient approach to the problem, especially in large-scale applications. It exploits the problem structure and hence is able to identify infeasible data more easily as well.}, file = {:by-author/D/Dong/2002_Dong_365.pdf:PDF}, keywords = {Distance geometry; distance matrix; strucure reconstruction}, owner = {saulius}, timestamp = {2011.12.14}, } @Article{Ferro1977, author = {Dino R. Ferro and Jan Hermans}, journal = {Acta Crystallographica Section A}, title = {A different best rigid-body molecular fit routine}, year = {1977}, pages = {345--347}, volume = {33}, abstract = {A different algorithm which gives a least-squares fit between two sets of atoms is described [cf. Nyburg (1974). Acta Cryst. B30, 251-253]. With this algorithm the coordinates of the moving set of atoms are changed only once.}, doi = {10.1107/S0567739477000862}, file = {:by-author/F/Ferro/1977_Ferro_345.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {xray crystallography, algorithms, structure superposition}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://scripts.iucr.org/cgi-bin/paper?S0567739477000862}, } @Article{Flower1999, author = {Flower, D. R.}, journal = {J Mol Graph Model}, title = {Rotational Superposition: A Review of Methods}, year = {1999}, pages = {238--244}, volume = {17}, abstract = {Rotational superposition is one of the most commonly used algorithms in molecular modelling. Many different methods of solving superposition have been suggested. Of these, methods based on the quaternion parameterization of rotation are fast, accurate, and robust. Quaternion parameterization-based methods cannot result in rotation inversion and do not have special cases such as co-linearity or co-planarity of points. Thus, quaternion parameterization-based methods are the best choice for rotational superposition applications.}, file = {:by-author/F/Flower/1999_Flower_238.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition, review}, owner = {saulius}, timestamp = {2012.05.16}, } @Article{Gao2010, author = {Fuchang Gao and Lixing Han}, journal = {Computational Optimization and Applications}, title = {Implementing the Nelder-Mead simplex algorithm with adaptive parameters}, year = {2010}, issn = {0926-6003}, pages = {259--277}, volume = {51}, doi = {10.1007/s10589-010-9329-3}, file = {:by-author/G/Gao/2010_Gao_259.pdf:PDF}, issue = {1}, keywords = {CS, minimisation, simplex method}, owner = {saulius}, publisher = {Springer US}, timestamp = {2012.10.21}, url = {http://dx.doi.org/10.1007/s10589-010-9329-3}, } @Article{Hendrickson1979, author = {Wayne A. Hendrickson}, journal = {Acta Crystallographica Section A}, title = {Transformations to Optimize the Superposition of Similar Structures}, year = {1979}, pages = {158--163}, volume = {35}, abstract = {A simple, efficient and general method is described for finding the linear orthogonal transformation to superpose two similar structures given by sets of equivalent points, usually atomic position vectors. Formulae are also given for extracting the independent variables of rotation from the resulting transformation matrix. In addition, general transformations are derived, both in the case of proper rotation and in the case of rotatory inversion, to convert to a molecular frame of reference based on the superposition axis of symmetry.}, doi = {10.1107/S0567739479000279}, file = {:by-author/H/Hendrickson/1979_Hendrickson_158.pdf:PDF}, keywords = {xray crystallography, algorithms}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://scripts.iucr.org/cgi-bin/paper?S0567739479000279}, } @Article{Horn1987, author = {Berthold K. P. Horn}, journal = {Journal of the Optical Society of America A}, title = {Closed-form solution of absolute orientation using unit quaternions}, year = {1987}, pages = {629--642}, volume = {4}, doi = {10.1364/JOSAA.4.000629}, file = {:by-author/H/Horn/1987_Horn_629.pdf:PDF;manuscript:by-author/H/Horn/1999_Horn_manuscript.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {quaternions, structure superposition, algorithms}, owner = {saulius}, timestamp = {2012.05.16}, } @Article{Iwase1999, author = {Iwase, Kazuhiko and Hirono, Shuichi}, journal = {Journal of Computer-Aided Molecular Design}, title = {Estimation of active conformations of drugs by a new molecular superposing procedure}, year = {1999}, issn = {0920-654X}, pages = {499--512}, volume = {13}, abstract = {We have developed a new program, SUPERPOSE, to superpose two molecules based on the physicochemical properties of functional atoms within individual molecules. SUPERPOSE treats a pseudo-molecule consisting of functional atoms instead of a real molecule. Four types of physicochemical properties – hydrophobicity, presence of a hydrogen-bonding donor, presence of a hydrogen-bonding acceptor and presence of a hydrogen-bonding donor/acceptor – were supposed and a score was given to each overlap. When functional atoms with the same physicochemical properties were overlapped, points were added to the score, and when the functional atoms with different physicochemical properties were overlapped, points were subtracted. We applied SUPERPOSE to 12 pairs of 24 enzyme inhibitors and found that the best scored overlay for each inhibitor pair could successfully reproduce the superposition obtained from X-ray crystallography. Next, we applied SUPERPOSE to estimate the active conformations of the thrombin inhibitors MQPA, 4-TAPAP and NAPAP. Superpositions of conformers sampled by the high-temperature molecular dynamics calculation with respect to the three inhibitors were performed, and 13 sets of conformers having the best common overlay to the three inhibitors were selected. One among 13 sets was consistent with the superposition of the active conformations derived from the X-ray crystallography of the thrombin–inhibitor complexes.}, file = {1999_Iwase_499.pdf:by-author/I/Iwase/1999_Iwase_499.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, issue = {5}, keywords = {structure superposition, algorithms}, owner = {saulius}, publisher = {Springer Netherlands}, timestamp = {2012.05.16}, url = {http://dx.doi.org/10.1023/A:1008011422113}, } @Article{Jewett2003, author = {Jewett, Andrew I. and Huang, Conrad C. and Ferrin, Thomas E.}, journal = {Bioinformatics}, title = {MINRMS: an efficient algorithm for determining protein structure similarity using root-mean-squared-distance}, year = {2003}, pages = {625--634}, volume = {19}, abstract = {Motivation: Existing algorithms for automated protein structure alignment generate contradictory results and are difficult to interpret. An algorithm which can provide a context for interpreting the alignment and uses a simple method to characterize protein structure similarity is needed.Results: We describe a heuristic for limiting the search space for structure alignment comparisons between two proteins, and an algorithm for finding minimal root-mean-squared-distance (RMSD) alignments as a function of the number of matching residue pairs within this limited search space. Our alignment algorithm uses coordinates of alpha-carbon atoms to represent each amino acid residue and requires a total computation time of O(m3 n2), where m and n denote the lengths of the protein sequences. This makes our method fast enough for comparisons of moderate-size proteins (fewer than ∼800 residues) on current workstation-class computers and therefore addresses the need for a systematic analysis of multiple plausible shape similarities between two proteins using a widely accepted comparison metric.Availability: See http://www.cgl.ucsf.edu/Research/minrmsContact: tef@cgl.ucsf.edu}, doi = {10.1093/bioinformatics/btg035}, eprint = {http://bioinformatics.oxfordjournals.org/content/19/5/625.full.pdf+html}, file = {2003_Jewett_625.pdf:by-author/J/Jewett/2003_Jewett_625.pdf:PDF}, owner = {saulius}, timestamp = {2012.12.02}, url = {http://bioinformatics.oxfordjournals.org/content/19/5/625.abstract}, } @Article{Karney2007, author = {Karney, Charles F. F.}, journal = {Journal of molecular graphics \& modelling}, title = {Quaternions in molecular modeling.}, year = {2007}, pages = {595--604}, volume = {25}, abstract = {Quaternions are an important tool to describe the orientation of a molecule. This paper considers the use of quaternions in matching two conformations of a molecule, in interpolating rotations, in performing statistics on orientational data, in the random sampling of rotations, and in establishing grids in orientation space. These examples show that many of the rotational problems that arise in molecular modeling may be handled simply and efficiently using quaternions.}, doi = {10.1016/j.jmgm.2006.04.002}, file = {manuscript:by-author/K/Karney/2006_Karney_manuscript.pdf:PDF;:by-author/K/Karney/2007_Karney_595.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition, quaternions}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{Lavery1989, author = {R. Lavery and H. Sklenar}, journal = {J. Biomol. Struct. Dyn.}, title = {Defining the structure of irregular nucleic acids: conventions and principles.}, year = {1989}, month = {Feb}, number = {4}, pages = {655--667}, volume = {6}, abstract = {The algorithm "Curves", that we have recently presented in this journal (J. Biolmol. Str. Dynam. 6, 63-91 (1988], is updated to take into account the conventions developed at the Cambridge meeting on DNA curvature (September 1988) and extended to the calculation of local parameters. In addition, the principles which govern the choices made in establishing the Curves algorithm are compared with the approaches adopted by other authors.}, doi = {10.1080/07391102.1989.10507728}, file = {1989_Lavery_655.pdf:by-author/L/Lavery/1989_Lavery_655.pdf:PDF}, institution = {Institut de Biologie Physico-Chimique, Paris, France.}, keywords = {Algorithms, DNA, Nucleic Acid Conformation}, language = {eng}, medline-pst = {ppublish}, owner = {em}, pmid = {2619933}, timestamp = {2011.07.13}, } @Article{Lavery1988, author = {R. Lavery and H. Sklenar}, journal = {J Biomol Struct Dyn}, title = {The definition of generalized helicoidal parameters and of axis curvature for irregular nucleic acids.}, year = {1988}, month = {Aug}, number = {1}, pages = {63--91}, volume = {6}, abstract = {An algorithm is presented which solves the problem of obtaining a rigorous helicoidal description of an irregular nucleic acid segment. Central to this approach is the definition of a function describing simultaneously the curvature of the nucleic acid segment in question and the corresponding stepwise variation of helicoidal parameters along the segment. Minimisation of this function leads to an optimal distribution of the conformational irregularity of the segment between these two components. Further, it is shown that this approach can be applied equally easily to single or double stranded nucleic acids. The results of this analysis yield both the absolute helicoidal parameters of individual bases/base pairs and the relative helicoidal parameters between successive bases/base pairs as well as the overall locus of the helical axis. The possibilities of this mathematical approach are demonstrated with the help of a computer program termed "Curves" which is applied to the study of a number of different nucleic acid structures.}, file = {1988_Lavery_63.pdf:by-author/L/Lavery/1988_Lavery_63.pdf:PDF}, institution = {Institut de Biologie Physico-Chimique, Paris, France.}, keywords = {Algorithms, Anticodon, Base Composition, Base Sequence, Chemistry, Physical; Crystallography; DNA, analysis; Models, Genetic; Models, Molecular; Nucleic Acid Conformation; Physicochemical Phenomena; RNA, analysis}, language = {eng}, medline-pst = {ppublish}, owner = {em}, pmid = {2482765}, timestamp = {2011.07.13}, } @Misc{Lavor2007, author = {Carlile Lavor and Leo Liberti and Nelson Maculan}, title = {An overview of distinct approaches for the molecular distance geometry problem}, year = {2007}, abstract = {We present a general overview of some of the most recent approaches for solving the molecular distance geometry problem, namely, the ABBIE algorithm, the DGSOL algorithm, d.c. optimization algorithms, the geometric build-up algorithm, and the BP algorithm.}, file = {:by-author/L/Lavor/2007_Lavor.pdf:PDF}, owner = {saulius}, timestamp = {2011.12.14}, } @InProceedings{Lavor2010, author = {Lavor, C. and Liberti, L. and Mucherino, A.}, booktitle = {Bioinformatics and Biomedicine Workshops (BIBMW), 2010 IEEE International Conference on}, title = {On the solution of molecular distance geometry problems with interval data}, year = {2010}, month = {dec.}, pages = {77 -82}, abstract = {The Molecular Distance Geometry Problem consists in finding the three-dimensional conformation of a protein using some of the distances between its atoms provided by experiments of Nuclear Magnetic Resonance. This is a continuous search problem that can be discretized under some assumptions on the known distances. We discuss the case where some of the distances are subject to uncertainty within a given nonnegative interval. We show that a discretization is still possible and propose an algorithm to solve the problem. Computational experiments on a set of artificially generated instances are presented.}, doi = {10.1109/BIBMW.2010.5703777}, file = {:by-author/L/Lavor/2010_Lavor_77.pdf:PDF}, keywords = {discretization, molecular distance geometry problem, nuclear magnetic resonance, protein data bank, search problem, three-dimensional protein conformation, bioinformatics, biological NMR, data acquisition, macromolecules, molecular biophysics, molecular configurations, proteins, search problems}, owner = {saulius}, timestamp = {2008.07.28}, } @Article{Li2009, author = {Yunqi Li and Ambrish Roy and Yang Zhang}, journal = {PLoS ONE}, title = {HAAD: A Quick Algorithm for Accurate Prediction of Hydrogen Atoms in Protein Structures}, year = {2009}, pages = {e6701}, volume = {4}, abstract = {Hydrogen constitutes nearly half of all atoms in proteins and their positions are essential for analyzing hydrogen-bonding interactions and refining atomic-level structures. However, most protein structures determined by experiments or computer prediction lack hydrogen coordinates. We present a new algorithm, HAAD, to predict the positions of hydrogen atoms based on the positions of heavy atoms. The algorithm is built on the basic rules of orbital hybridization followed by the optimization of steric repulsion and electrostatic interactions. We tested the algorithm using three independent data sets: ultra-high-resolution X-ray structures, structures determined by neutron diffraction, and NOE proton-proton distances. Compared with the widely used programs CHARMM and REDUCE, HAAD has a significantly higher accuracy, with the average RMSD of the predicted hydrogen atoms to the X-ray and neutron diffraction structures decreased by 26% and 11%, respectively. Furthermore, hydrogen atoms placed by HAAD have more matches with the NOE restraints and fewer clashes with heavy atoms. The average CPU cost by HAAD is 18 and 8 times lower than that of CHARMM and REDUCE, respectively. The significant advantage of HAAD in both the accuracy and the speed of the hydrogen additions should make HAAD a useful tool for the detailed study of protein structure and function. Both an executable and the source code of HAAD are freely available at http://zhang.bioinformatics.ku.edu/HAAD.}, doi = {10.1371/journal.pone.0006701}, file = {2009_Li_e6701.pdf:by-author/L/Li/2009_Li_e6701.pdf:PDF}, owner = {alexey}, timestamp = {2012.07.18}, } @Article{Liu2010a, author = {Pu Liu and Dimitris K. Agrafiotis and Douglas L. Theobald}, journal = {J. Comp. Chem.}, title = {Fast Determination of the Optimal Rotational Matrix for Macromolecular Superpositions}, year = {2010}, pages = {1561--1563}, volume = {31}, abstract = {Finding the rotational matrix that minimizes the sum of squared deviations between two vectors is an important problem in bioinformatics and crystallography. Traditional algorithms involve the inversion or decomposition of a 3 × 3 or 4 × 4 matrix, which can be computationally expensive and numerically unstable in certain cases. Here, we present a simple and robust algorithm to rapidly determine the optimal rotation using a Newton‐Raphson quaternion‐based method and an adjoint matrix. Our method is at least an order of magnitude more efficient than conventional inversion/decomposition methods, and it should be particularly useful for high‐throughput analyses of molecular conformations.}, doi = {10.1002/jcc.21439}, file = {:by-author/L/Liu/2010_Liu_1561.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{Liu2009, author = {Yu-Shen Liu and Yi Fang and Karthik Ramani}, journal = {BMC Bioinformatics}, title = {Using least median of squares for structural superposition of flexible proteins}, year = {2010}, pages = {10:29}, volume = {31}, doi = {10.1186/1471-2105-10-29}, file = {:by-author/L/Liu/2009_Liu_10-29.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{LoConte2000, author = {Lo Conte, Loredana and Ailey, Bart and Hubbard, Tim J. P. and Brenner, Steven E. and Murzin, Alexey G. and Chothia, Cyrus}, journal = {Nucleic Acids Research}, title = {SCOP: a Structural Classification of Proteins database}, year = {2000}, pages = {257--259}, volume = {28}, abstract = {The Structural Classification of Proteins (SCOP) database provides a detailed and comprehensive description of the relationships of known protein structures. The classification is on hierarchical levels: the first two levels, family and superfamily, describe near and distant evolutionary relationships; the third, fold, describes geometrical relationships. The distinction between evolutionary relationships and those that arise from the physics and chemistry of proteins is a feature that is unique to this database so far. The sequences of proteins in SCOP provide the basis of the ASTRAL sequence libraries that can be used as a source of data to calibrate sequence search algorithms and for the generation of statistics on, or selections of, protein structures. Links can be made from SCOP to PDB-ISL: a library containing sequences homologous to proteins of known structure. Sequences of proteins of unknown structure can be matched to distantly related proteins of known structure by using pairwise sequence comparison methods to find homologues in PDB-ISL. The database and its associated files are freely accessible from a number of WWW sites mirrored from URL http://scop.mrc-lmb. cam.ac.uk/scop/}, doi = {10.1093/nar/28.1.257}, eprint = {http://nar.oxfordjournals.org/content/28/1/257.full.pdf+html}, file = {LoConte_2000_257-SCOP.pdf:by-author/L/LoConte/2000_LoConte_257.pdf:PDF}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://nar.oxfordjournals.org/content/28/1/257.abstract}, } @Article{London2008a, author = {London, Nir and Schueler-Furman, Ora}, journal = {Structure (London, England : 1993)}, title = {Funnel hunting in a rough terrain: learning and discriminating native energy funnels.}, year = {2008}, pages = {269--79}, volume = {16}, abstract = {Protein folding and binding is commonly depicted as a search for the minimum energy conformation. Modeling of protein complex structures by RosettaDock often results in a set of low-energy conformations near the native structure. Ensembles of low-energy conformations can appear, however, in other regions, especially when backbone movements occur upon binding. What then characterizes the energy landscape near the correct orientation? We applied a machine learning algorithm to distinguish ensembles of low-energy conformations around the native conformation from other low-energy ensembles. The resulting classifier, FunHunt, identifies the native orientation in 50/52 protein complexes in a test set. The features used by FunHunt teach us about the nature of native interfaces. Remarkably, the energy decrease of trajectories toward near-native orientations is significantly larger than for other orientations. This provides a possible explanation for the stability of association in the native orientation.}, file = {:by-author/L/London/2008_London_269.pdf:PDF}, keywords = {protein folding}, owner = {saulius}, timestamp = {2012.10.21}, } @Article{Mackerell2004, author = {Mackerell, Alexander D. Jr}, journal = {Journal of Computational Chemistry}, title = {Empirical Force Fields for Biological Macromolecules: Overview and Issues}, year = {2004}, pages = {1584--1604}, abstract = {Empirical force field-based studies of biological macromolecules are becoming a common tool for investigating their structure–activity relationships at an atomic level of detail. Such studies facilitate interpretation of experimental data and allow for information not readily accessible to experimental methods to be obtained. A large part of the success of empirical force field-based methods is the quality of the force fields combined with the algorithmic advances that allow for more accurate reproduction of experimental observables. Presented is an overview of the issues associated with the development and application of empirical force fields to biomolecular systems. This is followed by a summary of the force fields commonly applied to the different classes of biomolecules; proteins, nucleic acids, lipids, and carbohydrates. In addition, issues associated with computational studies on “heterogeneous” biomolecular systems and the transferability of force fields to a wide range of organic molecules of pharmacological interest are discussed.}, file = {:by-author/M/Mackerell/2004_Mackerell_1584.pdf:PDF}, keywords = {forcefields}, owner = {andrius}, timestamp = {2012.05.07}, } @Article{Markley1988, author = {F. Landis Markley}, journal = {The Journal of Astronautical Sciences}, title = {Attitude Determination using Vector Observations and the Singular Value Decomposition}, year = {1988}, pages = {245--258}, volume = {38}, abstract = {A new method for finding the attitude matrix minimizing Wahba's loss function, based on the singular value decompisition of a 3x3 matrix, is presented. Equations are given for the covariance matrix of the attitude estimate, as wel as fo rthe eigenvalues and eigenvectors of this matrix, in terms of the singular value decomposition matrces. The singular value decomposition method is comared with Shuster's implementation of Davenport's q-method, which is more efficient than the new algorithm but does not give the eigenvalues and eigenvectors of the covariance matrix. These are often useful for analysis, since the maximum eigenvalue and its eigenvector fine the magnitude and direction of the largest component of the attitude uncertainty.}, file = {:by-author/M/Markley/1988_Markley_245.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{McLachlan1982, author = {McLachlan, A. D.}, journal = {Acta Crystallographica Section A}, title = {Rapid comparison of protein structures}, year = {1982}, issn = {1600-5724}, pages = {871--873}, volume = {38}, abstract = {An unusually fast method of superposing two sets of atomic coordinates for related molecular structures by least squares is described. It exploits the special nature of the problem and uses the method of conjugate gradients. The calculation takes about 0.003 s and is fast enough to be used in on-line graphics systems.}, doi = {10.1107/S0567739482001806}, file = {:by-author/M/McLachlan/1982_McLachlan_871.pdf:PDF}, keywords = {xray crystallography, algorithms}, owner = {saulius}, publisher = {International Union of Crystallography}, timestamp = {2008.07.28}, url = {http://dx.doi.org/10.1107/S0567739482001806}, } @Article{McLachlan1972, author = {McLachlan, A. D.}, journal = {Acta Crystallographica Section A}, title = {A mathematical procedure for superimposing atomic coordinates of proteins}, year = {1972}, pages = {656--657}, volume = {28}, abstract = {A procedure is given which determines the best rigid-body rotation and translation that matches a given set of measured atomic coordinates to a fixed set of guide coordinates and minimizes the weighted sum of squared deviations.}, doi = {10.1107/S0567739472001627}, file = {:by-author/M/McLachlan/1972_McLachlan_656.pdf:PDF}, keywords = {xray crystallography, algorithms}, owner = {saulius}, timestamp = {2008.07.28}, } @Article{Mechelke2010, author = {Martin Mechelke and Michael Habeck}, journal = {BMC Bioinformatics}, title = {Robust probabilistic superposition and comparison of protein structures}, year = {2010}, pages = {363}, volume = {11}, abstract = {Background Protein structure comparison is a central issue in structural bioinformatics. The standard dissimilarity measure for protein structures is the root mean square deviation (RMSD) of representative atom positions such as α-carbons. To evaluate the RMSD the structures under comparison must be superimposed optimally so as to minimize the RMSD. How to evaluate optimal fits becomes a matter of debate, if the structures contain regions which differ largely - a situation encountered in NMR ensembles and proteins undergoing large-scale conformational transitions. Results We present a probabilistic method for robust superposition and comparison of protein structures. Our method aims to identify the largest structurally invariant core. To do so, we model non-rigid displacements in protein structures with outlier-tolerant probability distributions. These distributions exhibit heavier tails than the Gaussian distribution underlying standard RMSD minimization and thus accommodate highly divergent structural regions. The drawback is that under a heavy-tailed model analytical expressions for the optimal superposition no longer exist. To circumvent this problem we work with a scale mixture representation, which implies a weighted RMSD. We develop two iterative procedures, an Expectation Maximization algorithm and a Gibbs sampler, to estimate the local weights, the optimal superposition, and the parameters of the heavy-tailed distribution. Applications demonstrate that heavy-tailed models capture differences between structures undergoing substantial conformational changes and can be used to assess the precision of NMR structures. By comparing Bayes factors we can automatically choose the most adequate model. Therefore our method is parameter-free. Conclusions Heavy-tailed distributions are well-suited to describe large-scale conformational differences in protein structures. A scale mixture representation facilitates the fitting of these distributions and enables outlier-tolerant superposition.}, doi = {10.1186/1471-2105-11-363}, file = {:by-author/M/Mechelke/2010_Mechelke_363.pdf:PDF}, groups = {sg/Bayesian}, owner = {saulius}, timestamp = {2011.12.21}, url = {http://www.biomedcentral.com/1471-2105/11/363}, } @InProceedings{Moreira2007, author = {Adriano Moreira and Maribel Yasmina Santos}, booktitle = {GRAPP 2007 - International Conference on Computer Graphics Theory and Applications}, title = {Concave hull: a k-nearest neighbours approach for the computation of the region occupied by a set of points}, year = {2007}, abstract = {This paper describes an algorit hm to compute the envelope of a set of points in a plane, which generates convex or non-convex hulls that represent the area occ upied by the given points. The proposed algorithm is based on a k -nearest neighbours approach, where the value of k , the only algorithm parameter, is used to control the “smoothness” of the final solution. The obtaine d results show that this algorithm is able to deal with arbitrary sets of points, and that the time to compute the polygons increases approxi mately linearly with the number of points.}, file = {2007_Moreira_61.pdf:by-author/M/Moreira/2007_Moreira_61.pdf:PDF}, groups = {sg/Concave Hull, sg/Bioinf. Algorithms}, keywords = {CS, algorithms, Concave hull, convex hull, polygon, contour, k-nearest neighbours}, owner = {saulius}, timestamp = {2015.12.16}, url = {https://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf}, } @Article{Morgan1965, author = {H. L. Morgan}, journal = {J. Chem. Doc.}, title = {The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service}, year = {1965}, pages = {107--113}, volume = {5}, doi = {10.1021/c160017a018}, file = {:by-author/M/Morgan/1965_Morgan_107.pdf:PDF}, keywords = {Morgan algorithm, chemoinformatics, databases, chemical database search, chemical fingerprint}, owner = {andrius}, timestamp = {2014.01.24}, } @Article{Murthy1984, author = {M.R.N. Murthy}, journal = {FEBS Letters}, title = {A fast method of comparing protein structures}, year = {1984}, issn = {0014-5793}, pages = {97--102}, volume = {168}, abstract = {Comparative studies on protein structures form an integral part of protein crystallography. Here, a fast method of comparing protein structures is presented. Protein structures are represented as a set of secondary structural elements. The method also provides information regarding preferred packing arrangements and evolutionary dynamics of secondary structural elements. This information is not easily obtained from previous methods. In contrast to those methods, the present one can be used only for proteins with some secondary structure. The method is illustrated with globin folds, cytochromes and dehydrogenases as examples.}, doi = {10.1016/0014-5793(84)80214-8}, file = {1984_Murthy_97.pdf:by-author/M/Murthy/1984_Murthy_97.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {Protein structure, Homology, Comparison, Evolution, Packing, Secondary structure, structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, url = {http://www.sciencedirect.com/science/article/pii/0014579384802148}, } @Article{Parsons2005, author = {Jerod Parsons and J. Bradley Holmes and J. Maurice Rojas and Jerry Tsai and Charlie E. M. Strauss}, journal = {Journal of computational chemistry}, title = {Practical conversion from torsion space to {C}artesian space for in silico protein synthesis.}, year = {2005}, pages = {1063}, volume = {26}, abstract = {Many applications require a method for translating a large list of bond angles and bond lengths to precise atomic Cartesian coordinates. This simple but computationally consuming task occurs ubiquitously in modeling proteins, DNA, and other polymers as well as in many other fields such as robotics. To find an optimal method, algorithms can be compared by a number of operations, speed, intrinsic numerical stability, and parallelization. We discuss five established methods for growing a protein backbone by serial chain extension from bond angles and bond lengths. We introduce the Natural Extension Reference Frame (NeRF) method developed for Rosetta's chain extension subroutine, as well as an improved implementation. In comparison to traditional two-step rotations, vector algebra, or Quaternion product algorithms, the NeRF algorithm is superior for this application: it requires 47% fewer floating point operations, demonstrates the best intrinsic numerical stability, and offers prospects for parallel processor acceleration. The NeRF formalism factors the mathematical operations of chain extension into two independent terms with orthogonal subsets of the dependent variables; the apparent irreducibility of these factors hint that the minimal operation set may have been identified. Benchmarks are made on Intel Pentium and Motorola PowerPC CPUs.}, doi = {10.1002/jcc.20237}, file = {:by-author/P/Parsons/2005_Parsons_1063.pdf:PDF}, keywords = {bioinformatics, Z-matrix, internal coordinates}, owner = {saulius}, timestamp = {2008.07.28}, } @Article{Pilati2000, author = {Pilati, Tullio and Forni, Alessandra}, journal = {Journal of Applied Crystallography}, title = {{\it SYMMOL} {--} a program to find the maximum symmetry in an atom cluster: an upgrade}, year = {2000}, pages = {417}, volume = {33}, doi = {10.1107/S0021889800001801}, file = {2000_Pilati_417.pdf:by-author/P/Pilati/2000_Pilati_417.pdf:PDF}, keywords = {maximum symmetry, atom clusters, algorithms, x-ray crystallography, spacegroups, symmetry}, owner = {saulius}, timestamp = {2015.06.15}, url = {http://dx.doi.org/10.1107/S0021889800001801}, } @Article{Pilati1998, author = {Pilati, T. and Forni, A.}, journal = {Journal of Applied Crystallography}, title = {{\it SYMMOL}: a program to find the maximum symmetry group in an atom cluster, given a prefixed tolerance}, year = {1998}, pages = {503--504}, volume = {31}, abstract = {{\it SYMMOL} is a new stand-alone program to find the maximum symmetry compatible with a given tolerance. The input requirements are cell parameters, atomic coordinates and the tolerance. The output is a set of symmetrized coordinates, the point-group label and the point-group elements. Some parameters quantifying the deviation from the exact symmetry are also calculated.}, doi = {10.1107/S0021889898002180}, file = {1998_Pilati_503.pdf:by-author/P/Pilati/1998_Pilati_503.pdf:PDF}, keywords = {x-ray crystallography, crystallographic software, algorithms}, owner = {saulius}, timestamp = {2015.06.15}, url = {http://dx.doi.org/10.1107/S0021889898002180}, } @Article{Schneider2002a, author = {Schneider, Thomas R.}, journal = {Acta Crystallographica Section D}, title = {A genetic algorithm for the identification of conformationally invariant regions in protein molecules}, year = {2002}, pages = {195--208}, volume = {58}, doi = {10.1107/S0907444901019291}, file = {jn0097.pdf:by-author/S/Schneider/2002_Schneider_195.pdf:PDF}, owner = {saulius}, timestamp = {2008.07.28}, url = {http://dx.doi.org/10.1107/S0907444901019291}, } @Article{Schneider2000, author = {Schneider, T. R.}, journal = {Acta crystallographica. Section D, Biological crystallography}, title = {Objective comparison of protein structures: error-scaled difference distance matrices.}, year = {2000}, pages = {714--21}, volume = {56}, abstract = {Understanding of macromolecular function in many cases relies on the comparison of related structural models. Commonly used least-squares superposition methods suffer from bias introduced into the comparison process by the subjective choice of atoms employed for the superposition. Difference distance matrices are a more objective means of comparing structures as they do not depend on a particular superposition scheme. However, they suffer from very high noise originating from coordinate errors. Modern refinement programs allow the rigorous estimation of standard uncertainties for individual atomic positions. These errors can be propagated through the calculation of a difference distance matrix allowing one to assess the significance level of structural differences. An algorithm is presented which produces an intuitive graphical representation of difference distance matrices after normalization to their error levels. Two examples where its application was revealing are described. Alternatives are suggested for cases where rigorous estimation of individual errors by the inversion of the full least-squares matrix is not feasible. The method offers an unbiased way to detect significant similarities and differences between related structures, as encountered in studies of complexes and mutants or when multiple models are obtained from experiments such as crystal structures involving non-crystallographic symmetry or different crystal modifications, or ensembles derived from NMR spectroscopy.}, file = {:by-author/S/Schneider/2000_Schneider_714.pdf:PDF}, keywords = {protein bioinformatics, structure comparison}, owner = {saulius}, timestamp = {2012.10.21}, } @Article{Schonemann1966, author = {Peter H. Schönemann}, journal = {Psychometrika}, title = {A generalized solution of the orthogonal Procrustes problem}, year = {1966}, pages = {1--10}, volume = {31}, abstract = {A solutionT of the least-squares problemAT=B +E, givenA andB so that trace (EprimeE)= minimum andTprimeT=I is presented. It is compared with a less general solution of the same problem which was given by Green [5]. The present solution, in contrast to Green's, is applicable to matricesA andB which are of less than full column rank. Some technical suggestions for the numerical computation ofT and an illustrative example are given. This paper is based on parts of a thesis submitted to the Graduate College of the University of Illinois in partial fulfillment of the requirements for a Ph.D. degree in Psychology. The work reported here was carried out while the author was employed by the Statistical Service Unit Research, U. of Illinois. It is a pleasure to express my appreciation to Prof. K. W. Dickman, director of this unit, for his continuous support and encouragement in this and other work. I also gratefully acknowledge my debt to Prof. L. Humphreys for suggesting the problem and to Prof. L. R. Tucker, who derived (1.7) and (1.8) in summation notation, suggested an iterative solution (not reported here) and who provided generous help and direction at all stages of the project.}, doi = {10.1007/BF02289451}, file = {:by-author/S/Schönemann/1996_Schönemann_1.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, url = {http://www.springerlink.com/content/l8023011278587w7/}, } @InProceedings{Shibberu2010, author = {Shibberu, Yosi and Holder, Allen and Lutz, Kyla}, booktitle = {Proceedings of the 6th international conference on Bioinformatics Research and Applications}, title = {Fast Protein Structure Alignment}, year = {2010}, address = {Berlin, Heidelberg}, pages = {152--165}, publisher = {Springer-Verlag}, series = {ISBRA'10}, doi = {10.1007/978-3-642-13078-6_18}, file = {:by-author/S/Shibberu/2010_Shibberu.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, isbn = {3-642-13077-1, 978-3-642-13077-9}, keywords = {structure superposition}, location = {Storrs, CT}, owner = {saulius}, timestamp = {2012.05.15}, url = {http://dx.doi.org/10.1007/978-3-642-13078-6_18}, } @Article{Steipe2002, author = {Steipe, Boris}, journal = {Acta Crystallographica Section A}, title = {A revised proof of the metric properties of optimally superimposed vector sets}, year = {2002}, pages = {506}, volume = {58}, abstract = {A revised proof is given that the root-mean-square deviation between more than two vector sets after optimal superposition induces a metric. This corrects an error in a previous manuscript [Kaindl & Steipe (1997). Acta Cryst. A53, 809].}, doi = {10.1107/S0108767302011637}, file = {2002_Steipe_506.pdf:by-author/S/Steipe/2002_Steipe_506.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {RMSD, structure superposition, proof, algorithms}, owner = {saulius}, timestamp = {2013.03.22}, url = {http://dx.doi.org/10.1107/S0108767302011637}, } @Article{Theobald2011, author = {Douglas L. Theobald and Kanti V. Mardia}, title = {Full {B}ayesian Analysis of the Generalized Non-isotropic {P}rocrustes Problem With Scaling}, year = {2011}, pages = {41}, file = {:by-author/T/Theobald/2011_Theobald_41.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bayesian, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{Theobald2012, author = {Theobald, Douglas L. and Steindel, Phillip A.}, journal = {Bioinformatics}, title = {Optimal Simultaneous Superpositioning of Multiple Structures With Missing Data}, year = {2012}, issn = {1367-4803}, pages = {1972--1979}, volume = {28}, address = {Oxford, UK}, doi = {10.1093/bioinformatics/bts243}, file = {:by-author/T/Theobald/2012_Theobald.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, publisher = {Oxford University Press}, timestamp = {2012.05.15}, url = {http://dx.doi.org/10.1093/bioinformatics/bts243}, } @Article{Theobald2006, author = {Theobald, Douglas L. and Wuttke, Deborah S.}, journal = {Bioinformatics (Oxford, England)}, title = {THESEUS: maximum likelihood superpositioning and analysis of macromolecular structures.}, year = {2006}, pages = {2171--2}, volume = {22}, abstract = {THESEUS is a command line program for performing maximum likelihood (ML) superpositions and analysis of macromolecular structures. While conventional superpositioning methods use ordinary least-squares (LS) as the optimization criterion, ML superpositions provide substantially improved accuracy by down-weighting variable structural regions and by correcting for correlations among atoms. ML superpositioning is robust and insensitive to the specific atoms included in the analysis, and thus it does not require subjective pruning of selected variable atomic coordinates. Output includes both likelihood-based and frequentist statistics for accurate evaluation of the adequacy of a superposition and for reliable analysis of structural similarities and differences. THESEUS performs principal components analysis for analyzing the complex correlations found among atoms within a structural ensemble. AVAILABILITY: ANSI C source code and selected binaries for various computing platforms are available under the GNU open source license from http://monkshood.colorado.edu/theseus/ or http://www.theseus3d.org.}, file = {:by-author/T/Theobald/2006_Theobald_2171.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {structure superposition}, owner = {saulius}, timestamp = {2012.05.15}, } @Article{Umeyama1991, author = {Shinji Umeyama}, journal = {IEEE Trans. Pattern Anal. Mach. Intell.}, title = {Least Squares Estimation of Transformation Parameters Between Two Point Sets}, year = {1991}, pages = {376--380}, volume = {13}, file = {1991_Umeyama_376.pdf:by-author/U/Umeyama/1991_Umeyama_376.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {algorithms, structure superposition}, owner = {saulius}, timestamp = {2012.05.16}, } @Article{Wang2012a, author = {Xueyi Wang and Jianmin Dong}, journal = {2012 2nd International Conference on Biomedical Engineering and Technology IPCBEE}, title = {A Normalized Weighted RMSD for Measuring Protein Structure Superposition}, year = {2012}, pages = {68--72}, volume = {34}, abstract = {Root-mean-square-deviation (RMSD) is the most widely used measure of the similarity of superimposed protein structures, but it is sensitive to outliers anda smaller RMSD value may not correspond to a better structure superposition. Many alternative measures have been proposed to overcome the deficiency in RMSD. In this paper, we extend the RMSD to normalized weighted RMSD (nwRMSD) to measure the quality of superimposed structures, where the nwRMSD assigns a normalized weight to eachsuperimposed position. We present an iterative algorithm to minimize nwRMSD for structure superposition and propose a new weight function for structure superposition. We show that NMR ensembles minimized by the nwRMSD measure can clearly display structurally conserved and flexible regions, which are better than the superposition in original structures.}, file = {:./by-author/W/Wang/2012_Wang_68.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {normalized weighted RMSD, structure superposition, position weight}, owner = {antanas}, timestamp = {2014.12.02}, } @Article{Zhang2005a, author = {Zhang, Yang and Skolnick, Jeffrey}, journal = {Nucleic acids research}, title = {TM-align: a protein structure alignment algorithm based on the TM-score.}, year = {2005}, pages = {2302--9}, volume = {33}, abstract = {We have developed TM-align, a new algorithm to identify the best structural alignment between protein pairs that combines the TM-score rotation matrix and Dynamic Programming (DP). The algorithm is approximately 4 times faster than CE and 20 times faster than DALI and SAL. On average, the resulting structure alignments have higher accuracy and coverage than those provided by these most often-used methods. TM-align is applied to an all-against-all structure comparison of 10 515 representative protein chains from the Protein Data Bank (PDB) with a sequence identity cutoff <95%: 1996 distinct folds are found when a TM-score threshold of 0.5 is used. We also use TM-align to match the models predicted by TASSER for solved non-homologous proteins in PDB. For both folded and misfolded models, TM-align can almost always find close structural analogs, with an average root mean square deviation, RMSD, of 3 A and 87% alignment coverage. Nevertheless, there exists a significant correlation between the correctness of the predicted structure and the structural similarity of the model to the other proteins in the PDB. This correlation could be used to assist in model selection in blind protein structure predictions. The TM-align program is freely downloadable at http://bioinformatics.buffalo.edu/TM-align.}, file = {:by-author/Z/Zhang/2005_Zhang_2302.pdf:PDF}, keywords = {protein bioinformatics, structure comparison}, owner = {saulius}, timestamp = {2012.10.21}, } @Article{Pulay1992, author = {P. Pulay and G. Fogarasi}, journal = {Journal of Chemical Physics}, title = {Geometry optimization in redundant internal coordinates}, year = {1992}, issn = {0021-9606}, number = {4}, pages = {2856--2860}, volume = {96}, abstract = {The gradient geometry-optimization procedure is reformulated in terms of redundant internal coordinates. By replacing the matrix inverse with the generalized inverse, the usual Newton-Raphson-type algorithms can be formulated in exactly the same way for redundant and nonredundant coordinates. Optimization in redundant coordinates is particularly useful for bridged polycyclic compounds and cage structures where it is difficult to define physically reasonable redundancy-free internal coordinates. This procedure, already used for the geometry optimization of porphine, C20N4H 14, is illustrated here at the ab initio self-consistent-field level for the four-membered ring azetidine, for bicyclo[2.2.2]octane, and for the four-ring system C16O2H22, the skeleton of taxol.}, doi = {10.1063/1.462844}, file = {:by-author/P/Pulay/1992_Pulay_2856.pdf:PDF}, keywords = {redundant internal coordinates, molecule optimisation}, language = {English}, owner = {saulius}, publisher = {American Institute of Physics Publising LLC}, timestamp = {2018.05.10}, } @Article{Glasser2020, author = {Leslie Glasser}, journal = {Journal of Applied Crystallography}, title = {From atoms to bonds, angles and torsions: molecular metrics from crystal space, and two {E}xcel implementations}, year = {2020}, month = {jul}, number = {4}, pages = {1--7}, volume = {53}, comment = {See 'by-author/G/Glasser/2020_Glasser_1_discussion/' for e-mails and files exchanged during a discussion. Clarifies formulae (6) and (2a).}, doi = {10.1107/s1600576720007311}, file = {:by-author/G/Glasser/2020_Glasser_1.pdf:PDF;:by-author/G/Glasser/2020_Glasser_1_suppl/gj5247sup3.pdf:PDF;:by-author/G/Glasser/2020_Glasser_1_suppl/gj5247sup1.xls:Excel;:by-author/G/Glasser/2020_Glasser_1_suppl/gj5247sup2.xlsx:Excel 2007+;:by-author/G/Glasser/2020_Glasser_1_discussion/2020-07-26_06_10_Leslie_Glasser_L.Glasser_at_exchange.curtin.edu.au.pdf:PDF}, keywords = {crystallography, teaching, algorithm, torion angles, bond angles, crystallographic computing}, owner = {saulius}, publisher = {International Union of Crystallography ({IUCr})}, timestamp = {2020.07.26}, } @Article{McDonald1994, author = {McDonald, I. K. and Thornton, J. M.}, journal = {Journal of molecular biology}, title = {Satisfying hydrogen bonding potential in proteins.}, year = {1994}, issn = {0022-2836}, month = may, pages = {777--793}, volume = {238}, abstract = {We have analysed the frequency with which potential hydrogen bond donors and acceptors are satisfied in protein molecules. There are a small percentage of nitrogen or oxygen atoms that do not form hydrogen bonds with either solvent or protein atoms, when standard criteria are used. For high resolution structures 9.5% and 5.1% of buried main-chain nitrogen and oxygen atoms, respectively, fail to hydrogen bond under our standard criteria, representing 5.8% and 2.1% of all main-chain nitrogen and oxygen atoms. We find that as the resolution of the data improves, the percentages fall. If the hydrogen bond criteria are relaxed many of these unsatisfied atoms form weak hydrogen bonds. However, there remain some buried atoms (1.3% NH and 1.8% CO) that fail to hydrogen bond without any immediately obvious compensating interactions.}, chemicals = {Amino Acids, Proteins, Hydrogen, Nitrogen, Oxygen}, citation-subset = {IM}, completed = {1994-06-16}, country = {England}, doi = {10.1006/jmbi.1994.1334}, file = {:by-author/M/McDonald/1994_McDonald_777.pdf:PDF}, issn-linking = {0022-2836}, issue = {5}, keywords = {Algorithms; Amino Acids, chemistry; Hydrogen, chemistry; Hydrogen Bonding; Nitrogen, chemistry; Oxygen, chemistry; Protein Structure, Secondary; Proteins, chemistry}, nlm-id = {2985088R}, owner = {saulius}, pii = {S0022-2836(84)71334-9}, pmid = {8182748}, pubmodel = {Print}, pubstate = {ppublish}, revised = {2013-11-21}, timestamp = {2021.04.19}, } @Article{Kaindl1997, author = {Kaindl, K. and Steipe, B.}, journal = {Acta Crystallographica Section A}, title = {Metric properties of the root-mean-square deviation of vector sets}, year = {1997}, pages = {809}, volume = {53}, abstract = {A proof is given that the root-mean-square deviation between more than two vector sets after optimal superposition induces a metric.}, doi = {10.1107/S0108767397010325}, file = {1997_Kaindl_809.pdf:by-author/K/Kaindl/1997_Kaindl_809.pdf:PDF}, groups = {sg/Molecule superposion, sg/Superposition, sg/Bioinf. Algorithms}, keywords = {RMSD, algorithms, proof, structure superposition}, owner = {saulius}, timestamp = {2013.03.22}, url = {http://dx.doi.org/10.1107/S0108767397010325}, } @Article{Steipe2002a, author = {Boris Steipe}, journal = {Acta Crystallographica Section A Foundations of Crystallography}, title = {Metric properties of the root-mean-square deviation of vector sets. Erratum}, year = {2002}, month = {aug}, number = {5}, pages = {507--507}, volume = {58}, doi = {10.1107/s0108767302012047}, file = {:by-author/S/Steipe/2002_Steipe_507.pdf:PDF}, keywords = {RMSD, algorithms, proof, structure superposition}, owner = {saulius}, publisher = {International Union of Crystallography ({IUCr})}, timestamp = {2022.03.01}, }