Bi-alignments with affine gaps costs
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 simil...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2022-05-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s13015-022-00219-7 |
| _version_ | 1811340736369524736 |
|---|---|
| author | Peter F. Stadler Sebastian Will |
| author_facet | Peter F. Stadler Sebastian Will |
| author_sort | Peter F. Stadler |
| collection | DOAJ |
| description | 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 ( $$\sim 930$$ ∼ 930 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. |
| first_indexed | 2024-04-13T18:46:18Z |
| format | Article |
| id | doaj.art-6e572c16203d4261b19c82849330ab89 |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-04-13T18:46:18Z |
| publishDate | 2022-05-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-6e572c16203d4261b19c82849330ab892022-12-22T02:34:34ZengBMCAlgorithms for Molecular Biology1748-71882022-05-0117111310.1186/s13015-022-00219-7Bi-alignments with affine gaps costsPeter F. Stadler0Sebastian Will1Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universität LeipzigAMIBio, Laboratoire d’Informatique de l’École Polytechnique (LIX), Institute Polytechnique de Paris (IP Paris)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 ( $$\sim 930$$ ∼ 930 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.https://doi.org/10.1186/s13015-022-00219-7Dynamic programmingScoring functionsMulti-tape formal grammarRecursion |
| spellingShingle | Peter F. Stadler Sebastian Will Bi-alignments with affine gaps costs Algorithms for Molecular Biology Dynamic programming Scoring functions Multi-tape formal grammar Recursion |
| title | Bi-alignments with affine gaps costs |
| title_full | Bi-alignments with affine gaps costs |
| title_fullStr | Bi-alignments with affine gaps costs |
| title_full_unstemmed | Bi-alignments with affine gaps costs |
| title_short | Bi-alignments with affine gaps costs |
| title_sort | bi alignments with affine gaps costs |
| topic | Dynamic programming Scoring functions Multi-tape formal grammar Recursion |
| url | https://doi.org/10.1186/s13015-022-00219-7 |
| work_keys_str_mv | AT peterfstadler bialignmentswithaffinegapscosts AT sebastianwill bialignmentswithaffinegapscosts |