Bi-alignments with Affine Gaps Costs

Overview

Journal Algorithms Mol Biol

Publisher Biomed Central

Date 2022 May 16

PMID 35578255

Authors

Peter F Stadler

Sebastian Will

Affiliations

Soon will be listed here.

Abstract

Background: Commonly, sequence and structure elements are assumed to evolve congruently, such that homologous sequence positions correspond to homologous structural features. Assuming congruent evolution, alignments based on sequence and structure similarity can therefore optimize both similarities at the same time in a single alignment. To model incongruent evolution, where sequence and structural features diverge positionally, we recently introduced bi-alignments. This generalization of sequence and structure-based alignments is best understood as alignments of two distinct pairwise alignments of the same entities: one modeling sequence similarity, the other structural similarity.

Results: Optimal bi-alignments with affine gap costs (or affine shift cost) for two constituent alignments can be computed exactly in quartic space and time. Even bi-alignments with affine shift and gap cost, as well as bi-alignment with sub-additive gap cost are optimized efficiently. Affine gap-cost bi-alignment of large proteins ([Formula: see text] aa) can be computed.

Conclusion: Affine cost bi-alignments are of practical interest to study shifts of protein sequences and protein structures relative to each other.

Availability: The affine cost bi-alignment algorithm has been implemented in Python 3 and Cython. It is available as free software from https://github.com/s-will/BiAlign/releases/tag/v0.3 and as bioconda package bialign.

Citing Articles

Comprehensive survey of conserved RNA secondary structures in full-genome alignment of Hepatitis C virus.

Triebel S, Lamkiewicz K, Ontiveros N, Sweeney B, Stadler P, Petrov A Sci Rep. 2024; 14(1):15145.

PMID: 38956134 PMC: 11219754. DOI: 10.1038/s41598-024-62897-0.

An ascomycete H4 variant with an unknown function.

Flipphi M, Harispe M, Hamari Z, Kocsube S, Scazzocchio C, Ramon A R Soc Open Sci. 2024; 11(2):231705.

PMID: 38384781 PMC: 10878826. DOI: 10.1098/rsos.231705.

References

Seton Bocco S, Csuros M . Splice Sites Seldom Slide: Intron Evolution in Oomycetes. Genome Biol Evol. 2016; 8(8):2340-50. PMC: 5010894. DOI: 10.1093/gbe/evw157. View

Baek M, DiMaio F, Anishchenko I, Dauparas J, Ovchinnikov S, Lee G . Accurate prediction of protein structures and interactions using a three-track neural network. Science. 2021; 373(6557):871-876. PMC: 7612213. DOI: 10.1126/science.abj8754. View

Lehmann J, Eisenhardt C, Stadler P, Krauss V . Some novel intron positions in conserved Drosophila genes are caused by intron sliding or tandem duplication. BMC Evol Biol. 2010; 10:156. PMC: 2891723. DOI: 10.1186/1471-2148-10-156. View

Eddy S . Where did the BLOSUM62 alignment score matrix come from?. Nat Biotechnol. 2004; 22(8):1035-6. DOI: 10.1038/nbt0804-1035. View

Cheng Li S . The difficulty of protein structure alignment under the RMSD. Algorithms Mol Biol. 2013; 8(1):1. PMC: 3599502. DOI: 10.1186/1748-7188-8-1. View

Kruspe M, Stadler P . Progressive multiple sequence alignments from triplets. BMC Bioinformatics. 2007; 8:254. PMC: 1948021. DOI: 10.1186/1471-2105-8-254. View

Gotoh O . An improved algorithm for matching biological sequences. J Mol Biol. 1982; 162(3):705-8. DOI: 10.1016/0022-2836(82)90398-9. View

Sankoff D . The early introduction of dynamic programming into computational biology. Bioinformatics. 2000; 16(1):41-7. DOI: 10.1093/bioinformatics/16.1.41. View

Hofacker I, Fekete M, Stadler P . Secondary structure prediction for aligned RNA sequences. J Mol Biol. 2002; 319(5):1059-66. DOI: 10.1016/S0022-2836(02)00308-X. View

10.

Chou P, Fasman G . Prediction of protein conformation. Biochemistry. 1974; 13(2):222-45. DOI: 10.1021/bi00699a002. View

11.

Hiller M, Findeiss S, Lein S, Marz M, Nickel C, Rose D . Conserved introns reveal novel transcripts in Drosophila melanogaster. Genome Res. 2009; 19(7):1289-300. PMC: 2704441. DOI: 10.1101/gr.090050.108. View

12.

Stadler P . Alignments of biomolecular contact maps. Interface Focus. 2021; 11(4):20200066. PMC: 8193466. DOI: 10.1098/rsfs.2020.0066. View

13.

Hare E, Peterson B, Iyer V, Meier R, Eisen M . Sepsid even-skipped enhancers are functionally conserved in Drosophila despite lack of sequence conservation. PLoS Genet. 2008; 4(6):e1000106. PMC: 2430619. DOI: 10.1371/journal.pgen.1000106. View

14.

Schultes E, Bartel D . One sequence, two ribozymes: implications for the emergence of new ribozyme folds. Science. 2000; 289(5478):448-52. DOI: 10.1126/science.289.5478.448. View

15.

Kabsch W, Sander C . On the use of sequence homologies to predict protein structure: identical pentapeptides can have completely different conformations. Proc Natl Acad Sci U S A. 1984; 81(4):1075-8. PMC: 344767. DOI: 10.1073/pnas.81.4.1075. View

16.

Poleksic A . Algorithms for optimal protein structure alignment. Bioinformatics. 2009; 25(21):2751-6. DOI: 10.1093/bioinformatics/btp530. View

17.

Lipman D, Altschul S, Kececioglu J . A tool for multiple sequence alignment. Proc Natl Acad Sci U S A. 1989; 86(12):4412-5. PMC: 287279. DOI: 10.1073/pnas.86.12.4412. View

18.

Bart A, Harris K, Gillam E, Scott E . Structure of an ancestral mammalian family 1B1 cytochrome P450 with increased thermostability. J Biol Chem. 2020; 295(17):5640-5653. PMC: 7186169. DOI: 10.1074/jbc.RA119.010727. View

19.

Dewey T . A sequence alignment algorithm with an arbitrary gap penalty function. J Comput Biol. 2001; 8(2):177-90. DOI: 10.1089/106652701300312931. View

20.

Jumper J, Evans R, Pritzel A, Green T, Figurnov M, Ronneberger O . Highly accurate protein structure prediction with AlphaFold. Nature. 2021; 596(7873):583-589. PMC: 8371605. DOI: 10.1038/s41586-021-03819-2. View