{"entities":{"Q1261853":{"pageid":1272603,"ns":120,"title":"Item:Q1261853","lastrevid":70024707,"modified":"2026-04-13T11:55:36Z","type":"item","id":"Q1261853","labels":{"en":{"language":"en","value":"Generalized sequence alignment and duality"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 409929"}},"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":"Q1261853$ACEB7941-C2A3-42F5-B08D-4B31A48F043F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"729194961b89bef3231fbcb2aa8371e2761c1b0d","datavalue":{"value":{"text":"Generalized sequence alignment and duality","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1261853$DA062A66-235A-4C20-A9C7-B31876EDF8A1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d3e1a5161f656de6af9b506a2ff690a9e9a46359","datavalue":{"value":"0810.92012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$95EA6FA3-FF5E-4F4A-BE26-98F9E4FBD731","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b512aa8e9f4008dff0e6be1454216b34f3afe087","datavalue":{"value":{"entity-type":"item","numeric-id":932315,"id":"Q932315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261853$7160D938-E72C-4DAC-9C5E-B6A3275F8550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8207abe0e0ba0a835bd033756c6fe396f59af93a","datavalue":{"value":{"entity-type":"item","numeric-id":242889,"id":"Q242889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261853$A11D5584-3B41-4570-AC39-8833499FAD5A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f171e2d358ed0c5ffcfe728031d35021527481f7","datavalue":{"value":{"entity-type":"item","numeric-id":103557,"id":"Q103557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261853$F586B171-E8C7-487E-8602-9775672412B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73e5a8ea7b61dfc367ebac864c9dbd92433ac1db","datavalue":{"value":{"time":"+1993-09-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1261853$C0DFDCA7-E080-4CAD-9110-554DF8557C4E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8f0292eb79094c85c15c46be241ec63037114430","datavalue":{"value":"The problem of finding a longest common subsequence of two sequences \\(s_ 1\\), \\(s_ 2, \\dots, s_ n\\) and \\(t_ 1\\), \\(t_ 2, \\dots, t_ m\\) (LCS-problem) can be characterized within the theory of posets by studying a partial order on \\(\\{1,2, \\dots, n\\} \\times \\{1,2, \\dots,m\\}\\) that is defined by means of a \\(2 \\times 2\\)-matrix \\(A\\) over 0 and 1. By allowing arbitrary integer matrices \\(A\\) the authors generalize the LCS- problem to a class of problems which includes several alignment problems that are of biological interest. For this class of A-LCS-problems a duality result is proved which is related to Dilworth's theorem on longest chain and minimum cover in posets and this result is utilized to give a primal-dual-algorithm for sequence alignments.   Moreover, algorithms for the A-CLS-problem based on the property of an A- LCS to be a path in a compatibility graph for a partial order are derived which generalize the classical dynamic programming approach, and it is shown that the A-CLS-problem is closely associated with the minimum Hilbert bases problem. The last part of the paper is devoted to generalized alignments. An algorithm for optimal generalized alignments is given that contains many alignment algorithms as particular cases.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$E8849CEE-C739-4CBC-8831-0093DDB918A4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cc6a2d1a81aec0cb5abdfe44055f934ac25329b","datavalue":{"value":"92C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$E0126CAA-1949-4F24-8D54-A0E4D3B4C667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$D7231211-E957-4342-BB85-576ED1B5D805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$0545DAD7-E0A5-4BEF-B988-F2DD40C0DBE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505a49771a29a1df80db47f27f0ca3c9ddd29e48","datavalue":{"value":"92D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$6000425A-9CE5-4852-B037-545FAA687AC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"96fda1f90957eed8ab5df9943245ade76812f72c","datavalue":{"value":"409929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$9ECB0B59-8A23-4FC2-82E7-631B5369738D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f0a0bf79411772273f5086c3d5a2f297706f321","datavalue":{"value":"longest common subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$78FEE537-86AA-4EBB-B207-5256CDEFEF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55ed4e02075ed4e4b1b42997cccad7cede0fb5bc","datavalue":{"value":"posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$88EDBBDC-1E06-4505-9B66-DD3E1BFE8EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a0ae4da02fbd7dafb649fea17ec9e92ddef210","datavalue":{"value":"A-LCS-problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$F63F7860-389A-4877-A164-66E8CA646B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4313a393a5e6beca51ade139c3d7f8791f5fe1f8","datavalue":{"value":"duality result","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$81A1E61E-F636-4F0E-99FC-C092B1B3E0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4d09e438694ec4bbdcb420829405ba32befaca3","datavalue":{"value":"Dilworth's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$66D63513-20A9-4B88-BCE6-EAA1D6F8B9D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f814b502294659bff614f9f8f8a00e9a90ab8ec","datavalue":{"value":"longest chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$1B0C0A53-281E-41E5-AF33-74A307BC3FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fdd57397953b197a7a731c5d8c94e730b1def40","datavalue":{"value":"minimum cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$73C120B6-0467-46AB-930C-46FEEE9A07E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f419cda1b4cab93dbf14d65c082fe568f92e279b","datavalue":{"value":"primal-dual-algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$994E7915-22FB-453A-BCD2-3361C1EBF3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a964123cc7dd9b58fee73d54577b7b3d9542945","datavalue":{"value":"sequence alignments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$A66015E9-D739-4B1A-998A-8F3360A2E1A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6dbf1d3a49cc7094970154d8b681001aae1c450","datavalue":{"value":"compatibility graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$73F6E090-08CF-4ED1-8C1D-6FBC947E5950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1788bf5d74b8eddff503e6b37a01d9e78eaa86c7","datavalue":{"value":"minimum Hilbert bases problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$943A7907-0A61-42DE-A2C3-0812DDD8EF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f8b25036796ed55d982e3c9b5835cbfc53109b","datavalue":{"value":"generalized alignments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261853$03175F85-5EEF-4D55-87E0-6585A7E3678C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"98a41ef3f4bac60e4673bcfc370d83882d60f068","datavalue":{"value":{"entity-type":"item","numeric-id":190392,"id":"Q190392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261853$4DCC3A32-E2AD-4B5A-A348-07BBA8467B78","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":"Q1261853$B8AE0726-C60F-454B-B8D9-FA294483DEE8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be4be270e3fe8bfd8a2326f837cf6ecf4c068234","datavalue":{"value":"https://doi.org/10.1006/aama.1993.1008","type":"string"},"datatype":"url"},"type":"statement","id":"Q1261853$005B315D-3300-4A73-9BB5-786E94A89960","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a21d07f985fdb698d7880044a503e5a32daf5118","datavalue":{"value":"W2036479856","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$A3D30BCC-E514-4070-A72A-9FC38960B8E9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e000cc04b8f80c49030e1a1815efc2535326bd2e","datavalue":{"value":"10.1006/AAMA.1993.1008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261853$C97106A8-3D56-4C59-A0A0-A12DFF597906","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ec329f76c3f3a3d76a2a3e8f5f4c3eca65a2def","datavalue":{"value":{"entity-type":"item","numeric-id":396006,"id":"Q396006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6a1eb3d52b0c2359f486fcf2db54789787abf88","datavalue":{"value":{"amount":"+0.7948563694953918","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":"Q1261853$71CC4B08-FE84-4585-85B9-8E3757F1675B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3347b2686a47e961fa919de7fb1dc4391ac6fad","datavalue":{"value":{"entity-type":"item","numeric-id":3798506,"id":"Q3798506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f50dada0f27a70d2349fa9e9323130ed4d37535a","datavalue":{"value":{"amount":"+0.7940543293952942","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":"Q1261853$09AE3A89-8F0C-46A2-94C5-249C58A77F89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421d24bbe38f4ee478548d783d3404ef0e7076c1","datavalue":{"value":{"entity-type":"item","numeric-id":5459135,"id":"Q5459135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd87eb4f98888bc9522aa79b10d7ee3e75fa3f1c","datavalue":{"value":{"amount":"+0.7922743558883667","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":"Q1261853$F50CBAE2-8922-4562-B935-5420CB3E8A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55def00298132f0a374f904e51202581c899c664","datavalue":{"value":{"entity-type":"item","numeric-id":4731046,"id":"Q4731046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87ee8d1ce40e806befbe42ee4bae9066ad9df10d","datavalue":{"value":{"amount":"+0.7856864929199219","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":"Q1261853$3D52C8FA-11FD-43D4-988F-73864C3DDEBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f39bff4e4cab39dfd1f0038f44c46a5c48384198","datavalue":{"value":{"entity-type":"item","numeric-id":497193,"id":"Q497193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"139fa58b984001a8e34d06b114b333aa449af189","datavalue":{"value":{"amount":"+0.7847658395767212","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":"Q1261853$3E8B58F8-9D58-4C41-8049-BD9372F5F38A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized sequence alignment and duality","badges":[]}}}}}