Dataset Information

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 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.

SUBMITTER: Stadler PF

PROVIDER: S-EPMC9109335 | biostudies-literature | 2022 May

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Bi-alignments with affine gaps costs.

Stadler Peter F PF Will Sebastian S

Algorithms for molecular biology : AMB 20220516 1

<h4>Background</h4>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 ...[more]

PMID: 35578255

Similar Datasets

Project description:IntroductionLinear programming (LP) is often used within diet optimization to find, from a set of available food commodities, the most affordable diet that meets the nutritional requirements of an individual or (sub)population. It is, however, not always possible to create a feasible diet, as certain nutritional requirements are difficult to meet. In that case, goal programming (GP) can be used to minimize deviations from the nutritional requirements in order to obtain a near feasible diet. With GP the cost of the diet is often overlooked or taken into account using the ε-constraint method. This method does not guarantee to find all possible trade-offs between costs and nutritional deficiency without solving many uninformative LPs.MethodsWe present a method to find all trade-offs between any two linear objectives in a dietary LP context that is simple, does not solve uninformative LPs and does not need prior input from the decision maker (DM). This method is a bi-objective algorithm based on the NonInferior Set Estimation (NISE) method that finds all efficient trade-offs between two linear objectives.ResultsIn order to show what type of insights can be gained from this approach, two analyses are presented that investigate the relation between cost and nutritional adequacy. In the first analysis a diet with a restriction on the exact energy intake is considered where all nutrient intakes except energy are allowed to deviate from their prescription. This analysis is especially helpful in case of a restrictive budget or when a nutritionally adequate diet is either unaffordable or unattainable. The second analysis only relaxes the exact energy intake, where the other nutrients are kept within their requirements, to investigate how the energy intake affects the cost of a diet. Here, we describe in what situations the so-called more-for-less paradox takes place, which can be induced by requiring an exact energy intake.ConclusionTo the best of our knowledge, we are the first to address how to obtain all efficient trade-offs of two linear objectives in a dietary LP context and how this can be used for analyses.

Dataset Information

Bi-alignments with affine gaps costs.

Background

Results

Conclusion

Availability

Publications

Bi-alignments with affine gaps costs.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets