Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict RNA secondary structure, are considered. These recurrences are defined over a number of points that is quadratic in the input size; however, only a sparse set matters for the result. Efficient algorithms are given for solving these problems, when the cost of a gap in the alignment or a loop in the secondary structure is taken as a convex or concave function of the gap or loop length. The time complexity of our algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse, this results in a substantial speed-up over known algorithms. © 1992, ACM. All rights reserved.
Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Bemali Wickramanayake, Zhipeng He, et al.
Knowledge-Based Systems
Susan L. Spraragen
International Conference on Design and Emotion 2010
Ryan Johnson, Ippokratis Pandis
CIDR 2013