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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∼</mml:mo> <mml:mn>930</mml:mn> </mml:mrow> </mml:math> 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 .

Peter F. Stadler

Sebastian Will

Algorithms for Molecular Biology

ALGORITHMS FOR MOLECULAR BIOLOGY 发表关于生物序列和结构分析、系统发育重建、组合算法和机器学习的新算法的文章。感兴趣的领域包括但不限于：RNA 和蛋白质结构分析算法、基因预测和基因组分析、比较序列分析和比对、系统发育、基因表达、机器学习和组合算法。在适当的情况下，手稿应描述对现实世界数据的应用。但是，如果预期未来将应用于生物数据，或者如果它们解决了分子生物学中新计算问题的复杂性或近似问题，那么纯算法论文也受到欢迎。如果有关新颖软件工具的文章包含一些算法上有趣的方面，则将被考虑发表。

The journal "Algorithms for Molecular Biology" publishes research articles on new algorithms related to biological sequence and structure analysis, phylogenetic reconstruction, combinatorial algorithms, and machine learning. Areas of interest include, but are not limited to: algorithms for RNA and protein structure analysis, gene prediction and genomic analysis, comparative sequence analysis and alignment, phylogenetics, gene expression, machine learning, and combinatorial algorithms. Manuscripts should describe applications to real-world data when appropriate. However, pure algorithm papers will also be welcomed if they are expected to be applied to biological data in the future or if they address the complexity or approximation issues of new computational problems in molecular biology. Articles that discuss novel software tools and include interesting algorithmic aspects will also be considered for publication.

《Algorithms for Molecular Biology》期刊发表关于生物序列和结构分析、系统发育重建、组合算法和机器学习的新算法的研究文章。感兴趣的领域包括但不限于：RNA和蛋白质结构分析算法、基因预测和基因组分析、比较序列分析和比对、系统发育、基因表达、机器学习和组合算法。在适当的情况下，手稿应描述对现实世界数据的应用。然而，如果预期未来将应用于生物数据，或者如果它们解决了分子生物学中新计算问题的复杂性或近似问题，那么纯算法论文也会受到欢迎。如果有关新颖软件工具的文章包含一些算法上有趣的方面，也将被考虑发表。

Category	Quartile
生物学	4
生物学, 生化研究方法	4
生物学, 生物工程与应用微生物	4
生物学, 数学与计算生物学	4

Bi-alignments with affine gaps costs

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info