DROPS

Artifact

Software

ProteinStructureAlignmentPlus

Authors: Masahito Tsukahara and Tetsuo Shibuya

Abstract

Cite as

@misc{dagpub-supp--paper-25847-urlgithub.com-masat03110-ProteinStructureAlignmentPlus,
   title = {{ProteinStructureAlignmentPlus}}, 
   author = {Tsukahara, Masahito and Shibuya, Tetsuo},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:8bdeadc1f4304d35619d3600f97069c17bc38192;origin=https://github.com/masat03110/ProteinStructureAlignmentPlus;visit=swh:1:snp:e5593dc75afb7e4f46874b2029bc5dd473034cba;anchor=swh:1:rev:be8e66b12f8ec7f679bda152b9fd254c23f27bc9}{\texttt{swh:1:dir:8bdeadc1f4304d35619d3600f97069c17bc38192}} (visited on 2026-08-27)},
   url = {https://github.com/masat03110/ProteinStructureAlignmentPlus},
}

Document

DOI: 10.4230/LIPIcs.WABI.2026.7

Theoretically and Practically Faster Algorithms for Protein Structure Alignment

Authors: Masahito Tsukahara and Tetsuo Shibuya

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract

Identifying shared substructures in 3D protein models is essential for structural bioinformatics. This task can be modeled as a sequential Largest Common Point-set (LCP) problem under the bottleneck distance. We propose a new O(n^13 log n)-time exact algorithm for this problem, which improves upon the previous best-known complexity of O(n^14), where n is the maximum size of the two input structures. Since these theoretical bounds are practically too large, an O(n⁷ log n)-time approximation algorithm with solution-size guarantees has been proposed; however, it remains too time-consuming for practical applications. Thus, we also propose a new filtering technique to enhance the approximation algorithm without increasing the theoretical time complexity or losing the solution-size guarantees. Experiments with PDB data show that our technique achieves over a 24-fold speedup at n = 130. While the previous algorithm required 3.80 hours on average for n = 130 in our experiments, making it difficult to test larger structures, our algorithm can process n = 200 in only 2.33 hours on average.

Cite as

Masahito Tsukahara and Tetsuo Shibuya. Theoretically and Practically Faster Algorithms for Protein Structure Alignment. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tsukahara_et_al:LIPIcs.WABI.2026.7,
  author =	{Tsukahara, Masahito and Shibuya, Tetsuo},
  title =	{{Theoretically and Practically Faster Algorithms for Protein Structure Alignment}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.7},
  URN =		{urn:nbn:de:0030-drops-275116},
  doi =		{10.4230/LIPIcs.WABI.2026.7},
  annote =	{Keywords: Structural Bioinformatics, Pairwise Alignment, Exact Algorithm, Approximation Algorithm, Computational Geometry}
}

Search Results

Documents authored by Tsukahara, Masahito

ProteinStructureAlignmentPlus

Abstract

Cite as

Theoretically and Practically Faster Algorithms for Protein Structure Alignment

Abstract

Cite as

Thanks for your feedback!

Could not send message