{"entities":{"Q1121182":{"pageid":1131931,"ns":120,"title":"Item:Q1121182","lastrevid":66797067,"modified":"2026-04-12T12:55:00Z","type":"item","id":"Q1121182","labels":{"en":{"language":"en","value":"Speeding up dynamic programming with applications to molecular biology"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4102840"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$6577E6EC-2311-4BD0-B52A-7738CE719914","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea4270dfd303410d45783f38f43efe69de9af7cb","datavalue":{"value":{"text":"Speeding up dynamic programming with applications to molecular biology","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1121182$068C23F1-DD1A-426D-B4FA-4F870CA98595","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"657088ff5bb2db8159cd796226235b13a1af7ca4","datavalue":{"value":"0673.90090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$B82E1999-7107-4B1E-B765-37F4EF996216","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e427d06588e0f5e6a2a228b1ad8e00160bd43819","datavalue":{"value":{"entity-type":"item","numeric-id":673782,"id":"Q673782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$8321BCFB-1846-48E8-9AF9-FD087532B085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea28a448642228799cca9ec32437afe18a704b31","datavalue":{"value":{"entity-type":"item","numeric-id":675051,"id":"Q675051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$E93ADF40-C41C-4814-921E-0FDA758BF41E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$EB6E0701-46F7-4314-931B-2B2CE8BB57F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1121182$726E8C9A-DD9F-485B-8776-3FE6F45198AA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"510e3139c16ee4e02f72f9cd7b813cc3f1c92ceb","datavalue":{"value":"Consider the problem of computing  \\[  E[j]=\\min_{0\\leq k\\leq j- 1}\\{D[k]+w(k,j)\\},\\quad j=1,...,n,  \\]  where w is a given weight function, D[0] is given and for every \\(k=1,...,n\\), D[k] is easily computable from E[k]. Obviously, it can be solved in time \\(O(n^ 2)\\), and for a general weight function no better algorithm is possible.    In this paper, two dual cases that arise in applications are considered: In the concave case, the weight function satisfies the quadrangle inequality:  \\[  w(k,j)+w(\\ell,j')\\leq w(\\ell,j)+w(k,j'),\\quad for\\quad all\\quad k\\leq \\ell \\leq j\\leq j'.  \\]  In the convex case, the weight function satisfies the inverse quadrangle inequality. In both cases it is shown how to use the assumed property of w to derive an O(n log n) algorithm. Even better, linear-time algorithms are obtained if w satisfies the following additional closest zero property: for every two integers \\(\\ell\\) and k, \\(\\ell <k\\), the real number a, the smallest zero of \\(f(x)=w(\\ell,x)-w(k,x)-a\\) which is larger than k can be found in constant time.    The two algorithms speed up several dynamic programming routines that solve as a subproblem the problem above. The speed-up is from \\(O(n^ 3)\\) to \\(O(n^ 2 \\log n)\\) or \\(O(n^ 2)\\). Applications include algorithms for comparing DNA sequences and algorithms used in speech recognition and geology. One typical problem is the following: Given the cost of substituting any pair of symbols and a convex cost function g for gaps (where g(r) is the cost of a gap of size r), compute the modified edit distance between the two given sequences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$9DA9F2AD-7214-4D25-B276-A1FED6D8EF3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$1F267567-F98D-4B20-B887-D09AEF3CAFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a784276b4e09d379c8147965411b455c3d79751","datavalue":{"value":"68T10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$763E19B1-72F4-4665-8FE5-7DF2F02E6024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfb5681686a479769f1498162f25169e468cda","datavalue":{"value":"92D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$32125B3F-2726-492E-8F8F-BD63582D9734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$EC73618F-8C12-4BF7-B480-D3076962CE2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f88427d2791ad08cc41803a706acb94f871edd9f","datavalue":{"value":"4102840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$8A358BD0-2026-4672-B2CF-321A66E2E24A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c87f5a8cf22007b9c36bf5f461676129bbe48ca","datavalue":{"value":"weight function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$4D3932DC-E891-4210-A272-4B9AB8CB08BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$E41DA597-3E2E-4E56-AB7B-A8C3F5AA1F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df479d6ff3ef0c265f317bc7d134c7b5665ddb9a","datavalue":{"value":"closest zero property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$DACDCAE2-A2B7-4C79-815E-BFE6A5D964D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72f0a44daff70f69bdf5ab8e07266ec0ed138053","datavalue":{"value":"DNA sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$BCCAC8A6-FF14-4696-B938-C17AF8921098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b8ad42826e30474ed4f80f300c2775642378dbb","datavalue":{"value":"speech recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$66F686AA-70E7-4E49-B745-7DCCA431BC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3612be778e5b1557d11b1e66350588626a56afd","datavalue":{"value":"geology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1121182$7DB39A34-0FEE-4D5D-B734-7E05924C906B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$98A73B61-21CE-4947-BBC6-D182EA6EC706","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1517810ef0dc593a66d9ddaf2a7c456793f39f0","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90101-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1121182$67ECDB7E-141C-4C15-B387-116CC3A3DC3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"43162d49bd24fe13999756f6d757b430d5ae6596","datavalue":{"value":"W2087817903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$BA58CBC1-BBCF-4616-BC48-57B730E075C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"da164dbdcc8d2593228e480cd917478b4ba505f6","datavalue":{"value":{"entity-type":"item","numeric-id":3796786,"id":"Q3796786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$126DB1D2-D86E-4A09-91C5-F158C21D7A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4fd2399a3704cf83726a1162abe2d51c058ed2e","datavalue":{"value":{"entity-type":"item","numeric-id":2551314,"id":"Q2551314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$4FDDB28C-AA5B-4327-8E43-DE2D49DFBD22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"291d98f4a6e2932a04cfae010493cfa7727b4875","datavalue":{"value":{"entity-type":"item","numeric-id":3926032,"id":"Q3926032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$E672B900-95E5-4CE4-9A79-9127CED99616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d21d2bbc9fd313be854a51e45563e56d629632fe","datavalue":{"value":{"entity-type":"item","numeric-id":1101364,"id":"Q1101364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$7EA6154C-3DBF-409A-AF70-FBCB87C57AF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cbbfd663e4cb8b866e390dba855e45e83f4fcd3","datavalue":{"value":{"entity-type":"item","numeric-id":799527,"id":"Q799527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$A6353B54-FCC3-489C-BB06-9C74915C5C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35d1904e2202079745d43a54b9e1cd4db59a1fc5","datavalue":{"value":{"entity-type":"item","numeric-id":3796787,"id":"Q3796787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$DE5E19F7-005F-4C38-96C9-BD89383557F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b22defaeda378cff96e4ee766f4074ea7b36a15","datavalue":{"value":{"entity-type":"item","numeric-id":3958292,"id":"Q3958292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1121182$EA340E7C-75E3-4B73-ACD7-6F2DFC836F84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf38e8d52304a3454ee5fbc8151fb1432c670053","datavalue":{"value":"10.1016/0304-3975(89)90101-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$98F235B3-B28A-44F1-9D38-91C2B434B335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P27","hash":"9dd3e4b1c948a73fd5f35fe84f92ca232949fc3d","datavalue":{"value":"10.7916/D8902BWC","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1121182$E0345BC4-08D0-4804-9559-E4091BB98A29","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25bdc55bdbf311fc5e94e42258caa6056de34403","datavalue":{"value":{"entity-type":"item","numeric-id":4302803,"id":"Q4302803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76e821921b9e4bc96b26b6a90c53a8a35eabb961","datavalue":{"value":{"amount":"+0.8627945780754089","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121182$5B18F5A5-3866-4EDC-834B-D83A77D22F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7097e55f233c3d288357e14e74082780642bdfea","datavalue":{"value":{"entity-type":"item","numeric-id":4763431,"id":"Q4763431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76e821921b9e4bc96b26b6a90c53a8a35eabb961","datavalue":{"value":{"amount":"+0.8627945780754089","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121182$693F8183-8230-4A44-8AF8-586F06BA6F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9f3dd5162855fd6f8e63781522e366a39495250","datavalue":{"value":{"entity-type":"item","numeric-id":4485189,"id":"Q4485189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f66fa8b74bbfb1fbc74cdab154f919b04a40cbfb","datavalue":{"value":{"amount":"+0.852745532989502","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121182$71558E74-BD82-49BA-A357-210B68399F19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef4eff9f4c5eab76fbf33efd6a8782f5791c3fdb","datavalue":{"value":{"entity-type":"item","numeric-id":1101364,"id":"Q1101364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b099ef509fe789fbcc82d88c9a8b8c3f5abba17","datavalue":{"value":{"amount":"+0.8518347144126892","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121182$FE18FD9E-6297-4AA0-AA1C-48A55FD94983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4be89db809b967bc9b25f8177f057f1ac8d809fa","datavalue":{"value":{"entity-type":"item","numeric-id":4302802,"id":"Q4302802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c51ec7493ed9f554ac5551e84bfc6c6f02219df3","datavalue":{"value":{"amount":"+0.8409230709075928","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1121182$86B96FB5-C583-41A2-8A4F-122A75BEA868","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Speeding up dynamic programming with applications to molecular biology","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Speeding_up_dynamic_programming_with_applications_to_molecular_biology"}}}}}