EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

epLSAP-Align: a non-sequential protein structural alignment solver with entropy-regularized partial linear sum assignment problem formulation

Xuechen Zhang iD, Zhuoyang Chen iD, Junyu Li iD, Qiong Luo iD, Longjun Wu iD, Weichuan Yu iD

Bioinformatics · 2025

DOI: 10.1093/bioinformatics/btaf309 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2025. Verfasst von Xuechen Zhang und 5 weiteren Autor:innen. Beteiligte Einrichtung: Department of Electronic and Computational Engineering, The Hong Kong University of Science and Technology, Hong Kong SAR, China. Hauptthemen laut MEDLINE: Algorithms, Proteins, Software, Sequence Alignment. Die Arbeit nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Center for Ocean Research in Hong Kong and Macau.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation The three-dimensional protein tertiary structure alignment is a fundamental problem that seeks insights into functions and evolution. Previous structure alignment algorithms have adopted the sequential assumption and used dynamic programming solvers. However, many distantly related structures exhibit non-sequential similarities, and non-sequential alignment tools are less efficient and accurate than sequential ones. In this paper, we formulate the non-sequential alignment as the Entropy-regularized Partial Linear Sum Assignment Problem (epLSAP) and propose a solver based on Sinkhorn algorithms, referred to as epLSAP-Align. Results Compared with existing non-sequential alignment solvers, our epLSAP-Align can explicitly model the gap penalty, efficiently achieve global optimality and balance coverage and fidelity. We show that epLSAP-Align can be easily integrated into the existing frameworks, such as TM-align and MICAN, resulting in the non-sequential alignment tool epLSAP-TM and epLSAP-MICAN, respectively. Both epLSAP-TM and epLSAP-MICAN achieve better performance than the existing non-sequential alignment tools in terms of biologically meaningful structure overlaps on two sequential alignment test sets MALIDUP and MALISAM, and four non-sequential alignment test sets MALIDUP-ns, MALISAM-ns, 64-difficult-case and RIPC datasets. Also, compared with the most recent non-sequential alignment tool USalign2, our epLSAP-TM is at least 22% faster under the same setting. Availability and implementation Our source code is available at https://github.com/xzhangem/epLSAP-align.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsProteinsSoftwareSequence AlignmentSequence Analysis, ProteinEntropyProtein Conformation

Substanzen

Proteins

Autor:innen und Institutionen

  • Department of Electronic and Computational Engineering, The Hong Kong University of Science and Technology, Hong Kong SAR, China.
  • Data Science and Analytics Thrust, Information Hub, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong 511400, China.
  • Department of Ocean Science and Center for Ocean Research in Hong Kong and Macau, The Hong Kong University of Science and Technology, Hong Kong SAR, China.
  • Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong SAR, China.

ORCID-Profile: Xuechen Zhang, Zhuoyang Chen, Junyu Li, Qiong Luo, Longjun Wu, Weichuan Yu

Förderung

  • Center for Ocean Research in Hong Kong and Macau

Zitieren

APA

Zhang, X., Chen, Z., Li, J., Luo, Q., Wu, L., & Yu, W. (2025). epLSAP-Align: a non-sequential protein structural alignment solver with entropy-regularized partial linear sum assignment problem formulation. Bioinformatics. https://doi.org/10.1093/bioinformatics/btaf309

Vancouver

Zhang X, Chen Z, Li J, Luo Q, Wu L, Yu W. epLSAP-Align: a non-sequential protein structural alignment solver with entropy-regularized partial linear sum assignment problem formulation. Bioinformatics. 2025. doi:10.1093/bioinformatics/btaf309

BibTeX
@article{Zhang2025,
  author = {Zhang, Xuechen and Chen, Zhuoyang and Li, Junyu and Luo, Qiong and Wu, Longjun and Yu, Weichuan},
  title = {epLSAP-Align: a non-sequential protein structural alignment solver with entropy-regularized partial linear sum assignment problem formulation},
  journal = {Bioinformatics},
  year = {2025},
  doi = {10.1093/bioinformatics/btaf309}
}
Kostenlos starten →