Svoboda | Graniru | BBC Russia | Golosameriki | Facebook

Sparse dynamic programming I: linear cost functions

Authors:

David Eppstein,

Raffaele Giancarlo,

Giuseppe F. ItalianoAuthors Info & Claims

Journal of the ACM (JACM), Volume 39, Issue 3

Pages 519 - 545

https://doi.org/10.1145/146637.146650

Published: 01 July 1992 Publication History

Abstract

Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction 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 for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the 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.

References

[1]

AGGARWAL, A., KLAWE, M. M., MORAN, S., SHOR, P., AND WILBER, R. Geomemc applications of a matrix-searching algorithm.

[2]

AGGARWAL, A., AND PARK, J. Searching in multidlmensional monotone matrices. In Proceedings of the 29th Annual Sympostum on Foundations of Computer Science. IEEE, New York, 1988, pp. 497-512.

[3]

AHo, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

[4]

AHo, A. V., HoPcRoFa', J. E., AND ULLMAN, J. D Data structures and algorithms. Addison- Wesley, Reading, Mass., 1983.

[5]

APosToLIco, A., AND GUERRA, C. The longest common subsequence problem revisited A Igorithmica 2 (1987), 315 - 336.

[6]

EPPSTEIN, D., GALIL, Z., AND GIANCARLO, R. Speeding up dynamic programming. In Proceedings of the 29th Symposium on the Foundations of Computer Science. IEEE, New York, 1988, pp. 488-496.

[7]

EPPSTEIN, D., GALIL, Z., GIANCARLO, R., AND ITALtANO, G.F. Sparse dynamic programming II: Convex and concave cost functions. J. ACM 39, 3 (July 1992), 546-567.

[8]

GAHL, Z., AND GIANCARLO, R. Speeding up dynamic programming with applications to molecular biology. Theoret. Comput. Sci. 64 (1989), 107-118.

[9]

JOHNSON, D.B. A priority queue in which initialization and queue operations take O(log log D) time. Math. Syst. Theory 15 (1982), 295-309.

[10]

H~RSCHB~.RG, D.S. Algorithms for the longest common subsequence problem. J. A CM 24, 4 (Oct. 1977), 664-675.

[11]

HIRSCHBERG, D. S., ANt) LARMORE, L. L. The least weight subsequence problem. SIAM J. Comput. 16 (1987), 628-638.

[12]

HUNT, J. W., AND SZYMANSKI, T. G. A fast algorithm for computing longest common subsequences. Commun. ACM20, 5 (May 1977), 350-353.

[13]

KANEmSI, M. I., AND GOAD, W. B. Pattern recognition in Nucleic Acid Sequences II: An efficient method for finding locally stable secondary structures. Nuc. Acids Res. IO, i (1982), 265-277.

[14]

KLAWt~, M. M., AND KLEtTMAN, D. An almost linear algorithm for generalized matrix searching. SIAM dr. Disc. Math. 3 (1990), 81 - 97.

[15]

KNua-H, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973.

[16]

LIPMAN, D. J., AND PEARSON, W.L. Rapid and Sensitive protein similarity searches. Science 2 (1985), 1435-1441.

[17]

MCCREmm~. E. M. A space-economical suffix tree construction algorithm. J. A CM 23, 2 (Apr. 1976), 262-272.

[18]

Mmf.F.R, W., AND MYERS, E.W. Sequence comparison with concave weighting functions. Bull. Math. Biol. 50, 2 (1988), 97-120.

[19]

NEEDLEMAN, S. B., AND WUNSCH, C. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48 (1970), 443.

[20]

SANKOFF, D., KURSKAL, J. B., MAINVILLE, S., AND CEDERGREEN, R. J. Fast algorithms to determine RNA secondary structures containing multiple loops. In D. Sankoff and J. B. Kruskal, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Mass., 1983. pp. 93-120.

[21]

TA~AN, R.E. Data Structures and Network Algorithms. SIAM, New York, 1985.

[22]

VAN EMDE BOAS, P. Preserving order in a forest in Less than logarithmic time. Inf. Proc. Lett. 6 (1977), 80-82.

[23]

WATERMAN, M. S., AND SMITH. T. F. RNA secondary structure: A complete mathematical analysis. Math, Biosci. 41 (1978), 257-266.

[24]

WATERMAN, M. S., AND SMITH, T. F. Rapid dynamic programming algorithms for RNA secondary structure. Adv. Appl. Math. 7 (1986), 455-464.

[25]

WATERMAN, M. S., SMITH, T. F. AND BEYER, W.A. Some biological sequence matrices. Adv. Math. 20 (1976), 367-387.

[26]

WHNEI~, P. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1-11.

[27]

WmBF~R, R. The concave least weight subsequence problem revisited. J. Algor. 9, 3 (1988), 418-425.

[28]

WILBUR, W. J., AND LIPMAN, D.J. Rapid similarity searches of nucleic acid and protein data banks. Proc. Nat. Acad. Sci. USA 80 (1983), 726-730.

[29]

WmBUR, W. J., AND LIPMAN, D.J. The context-dependent comparison of biological sequences. SIAM J. Appl. Math. 44, 3 (1984), 557-567.

Cited By

Saada BZhang TSiga EZhang JMagalhães Muniz M(2024)Whole-Genome Alignment: Methods, Challenges, and Future DirectionsApplied Sciences10.3390/app1411483714:11(4837)Online publication date: 3-Jun-2024
https://doi.org/10.3390/app14114837
Rajput JChandra GJain C(2024)Co-linear chaining on pangenome graphsAlgorithms for Molecular Biology10.1186/s13015-024-00250-w19:1Online publication date: 27-Jan-2024
https://doi.org/10.1186/s13015-024-00250-w
Ding XGu YSun YAgrawal KPetrank E(2024)Parallel and (Nearly) Work-Efficient Dynamic ProgrammingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659958(219-232)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659958
Show More Cited By

Index Terms

Sparse dynamic programming I: linear cost functions
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Sparse dynamic programming II: convex and concave cost functions

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 ...
Recovering sparse signals with a certain family of nonconvex penalties and DC programming

This paper considers the problem of recovering a sparse signal representation according to a signal dictionary. This problem could be formalized as a penalized least-squares problem in which sparsity is usually induced by a l₁-norm penalty on the ...
A combinatorial approach to a general two-term recurrence

We provide combinatorial proofs of explicit formulas for some sequences satisfying particular cases of the general recurrence |nk|=(@a(n-1)+@bk+@c)|n-1k|+(@a^'(n-1)+@b^'k+@c^')|n-1k-1|+[n=k=0], which have been previously shown using other methods. Many ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 39, Issue 3

July 1992

296 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/146637

Issue’s Table of Contents

Copyright © 1992 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Published in JACM Volume 39, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
1,967
Total Downloads

Downloads (Last 12 months)166
Downloads (Last 6 weeks)21

Reflects downloads up to 24 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saada BZhang TSiga EZhang JMagalhães Muniz M(2024)Whole-Genome Alignment: Methods, Challenges, and Future DirectionsApplied Sciences10.3390/app1411483714:11(4837)Online publication date: 3-Jun-2024
https://doi.org/10.3390/app14114837
Rajput JChandra GJain C(2024)Co-linear chaining on pangenome graphsAlgorithms for Molecular Biology10.1186/s13015-024-00250-w19:1Online publication date: 27-Jan-2024
https://doi.org/10.1186/s13015-024-00250-w
Ding XGu YSun YAgrawal KPetrank E(2024)Parallel and (Nearly) Work-Efficient Dynamic ProgrammingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659958(219-232)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659958
Liu YShen XGong YLiu YSong BZeng X(2023)Sequence Alignment/Map format: a comprehensive review of approaches and applicationsBriefings in Bioinformatics10.1093/bib/bbad32024:5Online publication date: 4-Sep-2023
https://doi.org/10.1093/bib/bbad320
Chandra GJain C(2023)Gap-Sensitive Colinear Chaining Algorithms for Acyclic Pangenome GraphsJournal of Computational Biology10.1089/cmb.2023.018630:11(1182-1197)Online publication date: 1-Nov-2023
https://doi.org/10.1089/cmb.2023.0186
Bzikadze APevzner P(2023)UniAligner: a parameter-free framework for fast sequence alignmentNature Methods10.1038/s41592-023-01970-420:9(1346-1354)Online publication date: 14-Aug-2023
https://doi.org/10.1038/s41592-023-01970-4
Chandra GJain C(2023)Sequence to Graph Alignment Using Gap-Sensitive Co-linear ChainingResearch in Computational Molecular Biology10.1007/978-3-031-29119-7_4(58-73)Online publication date: 16-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29119-7_4
Bringmann KCohen-Addad VDas D(2022)A Linear-Time n0.4-Approximation for Longest Common SubsequenceACM Transactions on Algorithms10.1145/356839819:1(1-24)Online publication date: 26-Oct-2022
https://dl.acm.org/doi/10.1145/3568398
Jain CGibney DThankachan S(2022)Algorithms for Colinear Chaining with Overlaps and Gap CostsJournal of Computational Biology10.1089/cmb.2022.026629:11(1237-1251)Online publication date: 1-Nov-2022
https://doi.org/10.1089/cmb.2022.0266
Jain CGibney DThankachan S(2022)Co-linear Chaining with Overlaps and Gap CostsResearch in Computational Molecular Biology10.1007/978-3-031-04749-7_15(246-262)Online publication date: 22-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-04749-7_15
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents