.png){kind=icon}
.png){kind=icon}
Return
Efficient and Accurate Approximation Algorithms for Protein Structure Alignment
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0698-9_11.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Detecting common substructures between three-dimensional (3D) protein structures is a fundamental problem in structural bioinformatics and drug discovery. This issue can be formulated as the wellknown geometric Largest Common Point-set (LCP) problem under the bottleneck distance. In this study, we focus on the order-dependent alignment variant. The fastest known exact algorithm for this variant has a time complexity of O(n32), whereas the fastest approximation algorithm with a theoretical guarantee runs in O(n8) time, where n is the size of the largest input structure. However, these algorithms suffer from impractical computational costs. Therefore, we propose two new approximation algorithms that improve efficiency and accuracy. The first algorithm optimizes an existing approach, achieving a reduced time complexity of O(n7 log n), whereas the second algorithm provides even greater efficiency under specific conditions. We implement these algorithms and evaluate their performance using datasets from the Protein Data Bank (PDB). Experimental results demonstrate that our proposed methods outperform existing algorithms in both efficiency and accuracy, indicating their suitability for real-world applications. The implementation is publicly available at: https://github.com/masat03110/sLCP.
Keywords:
Structural Bioinformatics
Pairwise Alignment
Approximation Algorithm
Computational Geometry
Journal
B
IF:
0
Papers:
25
Citations:
0