Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation
Entropy of multivariate distributions may be estimated based on the distances of nearest neighbours from each sample from a statistical ensemble. This technique has been applied on biomolecular systems for estimating both conformational and translational/rotational entropy. The degrees of freedom wh...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Biophysica |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2673-4125/2/4/31 |
| _version_ | 1827641510471925760 |
|---|---|
| author | Roberto Borelli Agostino Dovier Federico Fogolari |
| author_facet | Roberto Borelli Agostino Dovier Federico Fogolari |
| author_sort | Roberto Borelli |
| collection | DOAJ |
| description | Entropy of multivariate distributions may be estimated based on the distances of nearest neighbours from each sample from a statistical ensemble. This technique has been applied on biomolecular systems for estimating both conformational and translational/rotational entropy. The degrees of freedom which mostly define conformational entropy are torsion angles with their periodicity. In this work, tree structures and algorithms to quickly generate lists of nearest neighbours for periodic and non-periodic data are reviewed and applied to biomolecular conformations as described by torsion angles. The effect of dimensionality, number of samples, and number of neighbours on the computational time is assessed. The main conclusion is that using proper data structures and algorithms can greatly reduce the complexity of nearest neighbours lists generation, which is the bottleneck step in nearest neighbours entropy estimation. |
| first_indexed | 2024-03-09T17:15:54Z |
| format | Article |
| id | doaj.art-0cf92b7e7cc542aa9f05cea92dbbce81 |
| institution | Directory Open Access Journal |
| issn | 2673-4125 |
| language | English |
| last_indexed | 2024-03-09T17:15:54Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Biophysica |
| spelling | doaj.art-0cf92b7e7cc542aa9f05cea92dbbce812023-11-24T13:35:29ZengMDPI AGBiophysica2673-41252022-10-012434035210.3390/biophysica2040031Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy EstimationRoberto Borelli0Agostino Dovier1Federico Fogolari2Department of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, ItalyDepartment of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, ItalyDepartment of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, ItalyEntropy of multivariate distributions may be estimated based on the distances of nearest neighbours from each sample from a statistical ensemble. This technique has been applied on biomolecular systems for estimating both conformational and translational/rotational entropy. The degrees of freedom which mostly define conformational entropy are torsion angles with their periodicity. In this work, tree structures and algorithms to quickly generate lists of nearest neighbours for periodic and non-periodic data are reviewed and applied to biomolecular conformations as described by torsion angles. The effect of dimensionality, number of samples, and number of neighbours on the computational time is assessed. The main conclusion is that using proper data structures and algorithms can greatly reduce the complexity of nearest neighbours lists generation, which is the bottleneck step in nearest neighbours entropy estimation.https://www.mdpi.com/2673-4125/2/4/31entropyconformational entropynearest neighboursK-D treeVP-tree |
| spellingShingle | Roberto Borelli Agostino Dovier Federico Fogolari Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation Biophysica entropy conformational entropy nearest neighbours K-D tree VP-tree |
| title | Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation |
| title_full | Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation |
| title_fullStr | Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation |
| title_full_unstemmed | Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation |
| title_short | Data Structures and Algorithms for <i>k</i>-th Nearest Neighbours Conformational Entropy Estimation |
| title_sort | data structures and algorithms for i k i th nearest neighbours conformational entropy estimation |
| topic | entropy conformational entropy nearest neighbours K-D tree VP-tree |
| url | https://www.mdpi.com/2673-4125/2/4/31 |
| work_keys_str_mv | AT robertoborelli datastructuresandalgorithmsforikithnearestneighboursconformationalentropyestimation AT agostinodovier datastructuresandalgorithmsforikithnearestneighboursconformationalentropyestimation AT federicofogolari datastructuresandalgorithmsforikithnearestneighboursconformationalentropyestimation |