DOI: 10.1145/146637.146656. Sparse dynamic programming II

10.1145/146637.146656

Crossref journal-article

Association for Computing Machinery (ACM)

Journal of the ACM (320)

Abstract

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.

Bibliography

Eppstein, D., Galil, Z., Giancarlo, R., & Italiano, G. F. (1992). Sparse dynamic programming II. Journal of the ACM, 39(3), 546â567.

Authors 4

David Eppstein (first)
Zvi Galil (additional)
Raffaele Giancarlo (additional)
Giuseppe F. Italiano (additional)

References 31 Referenced 59

10.1016/0166-218X(90)90124-U
{'key': 'e_1_2_1_2_2', 'first-page': '497', 'volume-title': 'Proceedings of the 29th Symposium on Foundations of Computer Science IEEE', 'author': 'AGGARWAL A.', 'year': '1988'} / Proceedings of the 29th Symposium on Foundations of Computer Science IEEE by AGGARWAL A. (1988)
{'key': 'e_1_2_1_3_2', 'first-page': '209', 'article-title': 'Geometric applications of a matrix-searching algorithm', 'volume': '2', 'author': 'AGGARWAL A.', 'year': '1987', 'journal-title': 'Algomthmica'} / Algomthmica / Geometric applications of a matrix-searching algorithm by AGGARWAL A. (1987)
{'volume-title': 'Mass.', 'year': '1974', 'author': 'AHO A. V.', 'key': 'e_1_2_1_4_2'} / Mass. by AHO A. V. (1974)
10.1016/0196-6774(80)90015-2 / J. Algor. / Decomposable searching problems. I Static-to-dynamic transformation by BENTLEY J. L. (1980)
10.1016/0196-6774(90)90031-9
{'key': 'e_1_2_1_7_2', 'first-page': '488', 'volume-title': 'Proceedings of the 29th Syrnposzum on the Foundations of Computer Science. IEEE', 'author': 'EPPSTEIN D.', 'year': '1988'} / Proceedings of the 29th Syrnposzum on the Foundations of Computer Science. IEEE by EPPSTEIN D. (1988)
10.1145/146637.146650
10.1016/0304-3975(89)90101-1
10.1137/0216043
{'key': 'e_1_2_1_11_2', 'first-page': '317', 'volume-title': "Convexity. In Proceedings of the 7th Annual Symposium on Pure Mathematics. America'n Mathematical Society, Providence, R.I.", 'author': 'HOFFMAN A. J.', 'year': '1961'} / Convexity. In Proceedings of the 7th Annual Symposium on Pure Mathematics. America'n Mathematical Society, Providence, R.I. by HOFFMAN A. J. (1961)
10.1007/BF01786986 / Math. Syst. Theory / A priority queue in which initialization and queue operations take O(log log D) time by JOHNSON D.B (1982)
{'key': 'e_1_2_1_13_2', 'first-page': '1', 'article-title': 'Pattern recognition in Nucleic Acid Sequences II: An efficient method for finding locally stable secondary structures', 'volume': '10', 'author': 'KANEHISI M. I.', 'year': '1982', 'journal-title': 'Nuc. Acids Res.'} / Nuc. Acids Res. / Pattern recognition in Nucleic Acid Sequences II: An efficient method for finding locally stable secondary structures by KANEHISI M. I. (1982)
10.1137/0403009
{'volume-title': 'Mass.', 'year': '1973', 'author': 'KNUTH D. E.', 'key': 'e_1_2_1_15_2'} / Mass. by KNUTH D. E. (1973)
10.1002/spe.4380111102 / Softw. Pract. Exp. / Breaking paragraphs into lines by KN (1981)
LIPMAN D. J. AND PEARSON W.L. Rapid and Sensitive protein similarity searches Science 2 (1985) 1435-1441. LIPMAN D. J. AND PEARSON W.L. Rapid and Sensitive protein similarity searches Science 2 (1985) 1435-1441. (10.1126/science.2983426)
10.1016/S0092-8240(88)80016-8 / Bull. Math. Biol. / Sequence comparison with concave weighting functions by MILLER W. (1988)
{'volume-title': "Mdmoires de l'Acaddnlie des Sciences", 'author': 'MON~E G.', 'key': 'e_1_2_1_19_2'} / Mdmoires de l'Acaddnlie des Sciences by MON~E G.
10.1016/0022-2836(70)90057-4 / J. Mol. Biol. / A general method applicable to the search for similarities in the amino acid sequence of two proteins by NEEDLEMAN S. B. (1970)
{'key': 'e_1_2_1_21_2', 'first-page': '1', 'article-title': 'Algorithms for loop matchings', 'volume': '35', 'author': 'SSINOV R.', 'year': '1978', 'journal-title': 'SIAM J. Appl. Math.'} / SIAM J. Appl. Math. / Algorithms for loop matchings by SSINOV R. (1978)
{'key': 'e_1_2_1_22_2', 'first-page': '93', 'article-title': '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', 'author': 'SANKOFF D.', 'year': '1983', 'journal-title': 'Mass.'} / Mass. / 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 by SANKOFF D. (1983)
{'volume-title': 'SIAM', 'year': '1985', 'author': 'TARJAN R.E.', 'key': 'e_1_2_1_23_2'} / SIAM by TARJAN R.E. (1985)
10.1016/0020-0190(77)90031-X / Inf. Proc. Lett. / Preserving order in a forest in less than logarithmic tame by VAN EM BOAS (1977)
10.1016/0025-5564(78)90099-8 / Math. Biosci. / RNA secondary structure: A complete mathematical analysis by WATERMAN M. S. (1978)
10.1016/0196-8858(86)90025-4
10.1016/0001-8708(76)90202-4 / Adv. Math. / Some biological sequence matrices by WATERMAN M. S. (1976)
10.1016/0196-6774(88)90032-6
10.1073/pnas.80.3.726 / Proc. Nat. Acad. Sci. USA / Rapid similarity searches of nucleic acid and protein data banks by WILBUR W. J. (1983)
10.1137/0144038 / SIAM J. Appl. Math. / The context-dependent comparison of biological sequences by WILBUR W. J. (1984)
{'key': 'e_1_2_1_31_2', 'first-page': '429', 'volume-title': 'Proceedings of the 12th Annual A CM Symposium on the Theory of Computing', 'author': 'YAO F. F.', 'year': '1980'} / Proceedings of the 12th Annual A CM Symposium on the Theory of Computing by YAO F. F. (1980)

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:25 a.m.)
Deposited	2 months, 2 weeks ago (June 18, 2025, 4:22 p.m.)
Indexed	2 months, 1 week ago (June 30, 2025, 7:26 a.m.)
Issued	33 years, 2 months ago (July 1, 1992)
Published	33 years, 2 months ago (July 1, 1992)
Published Online	33 years, 2 months ago (July 1, 1992)
Published Print	33 years, 2 months ago (July 1, 1992)

Funders 0

None

BibTeX

@article{Eppstein_1992, title={Sparse dynamic programming II: convex and concave cost functions}, volume={39}, ISSN={1557-735X}, url={http://dx.doi.org/10.1145/146637.146656}, DOI={10.1145/146637.146656}, number={3}, journal={Journal of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Eppstein, David and Galil, Zvi and Giancarlo, Raffaele and Italiano, Giuseppe F.}, year={1992}, month=jul, pages={546–567} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        6,
        30
      ]
    ],
    "date-time": "2025-06-30T11:26:49Z",
    "timestamp": 1751282809792,
    "version": "3.41.0"
  },
  "reference-count": 31,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1992,
            7,
            1
          ]
        ],
        "date-time": "1992-07-01T00:00:00Z",
        "timestamp": 709948800000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1992,
        7
      ]
    ]
  },
  "abstract": "<jats:p>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.</jats:p>",
  "DOI": "10.1145/146637.146656",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:25:57Z",
    "timestamp": 1027769157000
  },
  "page": "546-567",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 59,
  "title": "Sparse dynamic programming II",
  "prefix": "10.1145",
  "volume": "39",
  "author": [
    {
      "given": "David",
      "family": "Eppstein",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Zvi",
      "family": "Galil",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Raffaele",
      "family": "Giancarlo",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Giuseppe F.",
      "family": "Italiano",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1992,
        7
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0166-218X(90)90124-U"
    },
    {
      "key": "e_1_2_1_2_2",
      "first-page": "497",
      "volume-title": "Proceedings of the 29th Symposium on Foundations of Computer Science IEEE",
      "author": "AGGARWAL A.",
      "year": "1988"
    },
    {
      "key": "e_1_2_1_3_2",
      "first-page": "209",
      "article-title": "Geometric applications of a matrix-searching algorithm",
      "volume": "2",
      "author": "AGGARWAL A.",
      "year": "1987",
      "journal-title": "Algomthmica"
    },
    {
      "volume-title": "Mass.",
      "year": "1974",
      "author": "AHO A. V.",
      "key": "e_1_2_1_4_2"
    },
    {
      "key": "e_1_2_1_5_2",
      "doi-asserted-by": "crossref",
      "first-page": "4",
      "DOI": "10.1016/0196-6774(80)90015-2",
      "article-title": "Decomposable searching problems. I Static-to-dynamic transformation",
      "volume": "1",
      "author": "BENTLEY J. L.",
      "year": "1980",
      "journal-title": "J. Algor."
    },
    {
      "key": "e_1_2_1_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0196-6774(90)90031-9"
    },
    {
      "key": "e_1_2_1_7_2",
      "first-page": "488",
      "volume-title": "Proceedings of the 29th Syrnposzum on the Foundations of Computer Science. IEEE",
      "author": "EPPSTEIN D.",
      "year": "1988"
    },
    {
      "key": "e_1_2_1_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/146637.146650"
    },
    {
      "key": "e_1_2_1_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0304-3975(89)90101-1"
    },
    {
      "key": "e_1_2_1_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0216043"
    },
    {
      "key": "e_1_2_1_11_2",
      "first-page": "317",
      "volume-title": "Convexity. In Proceedings of the 7th Annual Symposium on Pure Mathematics. America'n Mathematical Society, Providence, R.I.",
      "author": "HOFFMAN A. J.",
      "year": "1961"
    },
    {
      "key": "e_1_2_1_12_2",
      "doi-asserted-by": "crossref",
      "first-page": "295",
      "DOI": "10.1007/BF01786986",
      "article-title": "A priority queue in which initialization and queue operations take O(log log D) time",
      "volume": "15",
      "author": "JOHNSON D.B",
      "year": "1982",
      "journal-title": "Math. Syst. Theory"
    },
    {
      "key": "e_1_2_1_13_2",
      "first-page": "1",
      "article-title": "Pattern recognition in Nucleic Acid Sequences II: An efficient method for finding locally stable secondary structures",
      "volume": "10",
      "author": "KANEHISI M. I.",
      "year": "1982",
      "journal-title": "Nuc. Acids Res."
    },
    {
      "key": "e_1_2_1_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0403009"
    },
    {
      "volume-title": "Mass.",
      "year": "1973",
      "author": "KNUTH D. E.",
      "key": "e_1_2_1_15_2"
    },
    {
      "key": "e_1_2_1_16_2",
      "doi-asserted-by": "crossref",
      "first-page": "1119",
      "DOI": "10.1002/spe.4380111102",
      "article-title": "Breaking paragraphs into lines",
      "volume": "11",
      "author": "KN",
      "year": "1981",
      "journal-title": "Softw. Pract. Exp."
    },
    {
      "key": "e_1_2_1_17_2",
      "doi-asserted-by": "crossref",
      "unstructured": "LIPMAN D. J. AND PEARSON W.L. Rapid and Sensitive protein similarity searches Science 2 (1985) 1435-1441.  LIPMAN D. J. AND PEARSON W.L. Rapid and Sensitive protein similarity searches Science 2 (1985) 1435-1441.",
      "DOI": "10.1126/science.2983426"
    },
    {
      "key": "e_1_2_1_18_2",
      "doi-asserted-by": "crossref",
      "first-page": "2",
      "DOI": "10.1016/S0092-8240(88)80016-8",
      "article-title": "Sequence comparison with concave weighting functions",
      "volume": "50",
      "author": "MILLER W.",
      "year": "1988",
      "journal-title": "Bull. Math. Biol."
    },
    {
      "volume-title": "Mdmoires de l'Acaddnlie des Sciences",
      "author": "MON~E G.",
      "key": "e_1_2_1_19_2"
    },
    {
      "key": "e_1_2_1_20_2",
      "doi-asserted-by": "crossref",
      "first-page": "443",
      "DOI": "10.1016/0022-2836(70)90057-4",
      "article-title": "A general method applicable to the search for similarities in the amino acid sequence of two proteins",
      "volume": "48",
      "author": "NEEDLEMAN S. B.",
      "year": "1970",
      "journal-title": "J. Mol. Biol."
    },
    {
      "key": "e_1_2_1_21_2",
      "first-page": "1",
      "article-title": "Algorithms for loop matchings",
      "volume": "35",
      "author": "SSINOV R.",
      "year": "1978",
      "journal-title": "SIAM J. Appl. Math."
    },
    {
      "key": "e_1_2_1_22_2",
      "first-page": "93",
      "article-title": "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",
      "author": "SANKOFF D.",
      "year": "1983",
      "journal-title": "Mass."
    },
    {
      "volume-title": "SIAM",
      "year": "1985",
      "author": "TARJAN R.E.",
      "key": "e_1_2_1_23_2"
    },
    {
      "key": "e_1_2_1_24_2",
      "doi-asserted-by": "crossref",
      "first-page": "80",
      "DOI": "10.1016/0020-0190(77)90031-X",
      "article-title": "Preserving order in a forest in less than logarithmic tame",
      "volume": "6",
      "author": "VAN EM BOAS",
      "year": "1977",
      "journal-title": "Inf. Proc. Lett."
    },
    {
      "key": "e_1_2_1_25_2",
      "doi-asserted-by": "crossref",
      "first-page": "257",
      "DOI": "10.1016/0025-5564(78)90099-8",
      "article-title": "RNA secondary structure: A complete mathematical analysis",
      "volume": "42",
      "author": "WATERMAN M. S.",
      "year": "1978",
      "journal-title": "Math. Biosci."
    },
    {
      "key": "e_1_2_1_26_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0196-8858(86)90025-4"
    },
    {
      "key": "e_1_2_1_27_2",
      "doi-asserted-by": "crossref",
      "first-page": "367",
      "DOI": "10.1016/0001-8708(76)90202-4",
      "article-title": "Some biological sequence matrices",
      "volume": "20",
      "author": "WATERMAN M. S.",
      "year": "1976",
      "journal-title": "Adv. Math."
    },
    {
      "key": "e_1_2_1_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0196-6774(88)90032-6"
    },
    {
      "key": "e_1_2_1_29_2",
      "doi-asserted-by": "crossref",
      "first-page": "726",
      "DOI": "10.1073/pnas.80.3.726",
      "article-title": "Rapid similarity searches of nucleic acid and protein data banks",
      "volume": "80",
      "author": "WILBUR W. J.",
      "year": "1983",
      "journal-title": "Proc. Nat. Acad. Sci. USA"
    },
    {
      "key": "e_1_2_1_30_2",
      "doi-asserted-by": "crossref",
      "first-page": "3",
      "DOI": "10.1137/0144038",
      "article-title": "The context-dependent comparison of biological sequences",
      "volume": "44",
      "author": "WILBUR W. J.",
      "year": "1984",
      "journal-title": "SIAM J. Appl. Math."
    },
    {
      "key": "e_1_2_1_31_2",
      "first-page": "429",
      "volume-title": "Proceedings of the 12th Annual A CM Symposium on the Theory of Computing",
      "author": "YAO F. F.",
      "year": "1980"
    }
  ],
  "container-title": "Journal of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/146637.146656",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/146637.146656",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T20:22:07Z",
    "timestamp": 1750278127000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/146637.146656"
    }
  },
  "subtitle": [
    "convex and concave cost functions"
  ],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1992,
        7
      ]
    ]
  },
  "references-count": 31,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          1992,
          7
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/146637.146656"
  ],
  "URL": "http://dx.doi.org/10.1145/146637.146656",
  "relation": {},
  "ISSN": [
    "0004-5411",
    "1557-735X"
  ],
  "subject": [],
  "container-title-short": "J. ACM",
  "published": {
    "date-parts": [
      [
        1992,
        7
      ]
    ]
  },
  "assertion": [
    {
      "value": "1992-07-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}