{"entities":{"Q1085098":{"pageid":1095850,"ns":120,"title":"Item:Q1085098","lastrevid":66883380,"modified":"2026-04-12T13:30:23Z","type":"item","id":"Q1085098","labels":{"en":{"language":"en","value":"Optimal sequence alignment using affine gap costs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3980993"}},"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":"Q1085098$24B62AED-414C-484F-A9BA-6898D5435D9E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79b5d165157d7adb254036d24951f13311195c7a","datavalue":{"value":{"text":"Optimal sequence alignment using affine gap costs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1085098$9FCB79F1-B203-4623-B2BF-B7FDBF34AAB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fca269770cdb7c54eca8b7bb5b9d99bcd1ee2815","datavalue":{"value":"0606.92014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$9DA235A8-7607-4AE7-9721-B190EBCF5064","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ae59598b1136a27ac99f6dd56870d76cac9cae9","datavalue":{"value":"10.1007/BF02462326","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$6265B01C-46B6-4036-8005-5435B2048486","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e8240f28e3c9b6dd75737ee59e8f574cdfeb24c","datavalue":{"value":{"entity-type":"item","numeric-id":1085096,"id":"Q1085096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$A47C278C-21F6-43CE-BEB8-9A5684369F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b9f334a8a6e0fa31f67fbf7ba8e793627c0aeb3b","datavalue":{"value":{"entity-type":"item","numeric-id":1085097,"id":"Q1085097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$2AAB1EFC-F8A2-4EEC-99D8-DF80A09188A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4a6f7d015df5f02e6fe02ce89bcd002530eaade1","datavalue":{"value":{"entity-type":"item","numeric-id":85622,"id":"Q85622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$72E8438F-2D73-48AA-AB35-011D4D147C25","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1085098$2DD575E6-28E7-40A5-A06B-55B332511DAD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"369a62e8cdcb26391092764827ac41bc8fd15bd0","datavalue":{"value":"When comparing two biological sequences, it is often desirable for a gap to be assigned a cost not directly proportional to its length. If affine gap costs are employed, in other words if opening a gap costs v and each null in the gap costs u, the algorithm of \\textit{O. Gotoh} [J. molec, Biol. 162, 705-708 (1982)] finds the minimum cost of aligning two sequences in order MN steps. Gotoh's algorithm attempts to find only one from among possibly many optimal (minimum-cost) alignments, but does not always succeed.    This paper provides an example for which this part of Gotoh's algorithm fails and describes an algorithm that finds all and only the optimal alignments. This modification of Gotoh's algorithm still requires order MN steps. A more precise form of path graph than previously used is needed to represent accurately all optimal alignments for affine gap costs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$A117ECE3-953B-429D-B175-0B4FFEBB6586","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"408a79c1bfecc6ff58b5150b55e32f4d3c10746b","datavalue":{"value":"92Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$32888A9B-7868-44C4-8DAF-3FB0C3A0CD69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$E02A2523-8E3F-4BC0-ADB8-7C4A85BDDC37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$1100A909-086F-452D-B83E-592BEEA0B680","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0385f453a62211e67c4fdd830eb47f17cba098fd","datavalue":{"value":"3980993","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$031D432E-C03F-4568-8C42-0213AA819308","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4178eeb959aa707238abf34355427d0031bbd3d","datavalue":{"value":"biochemistry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$9A927236-48AA-4579-B1EF-DFA4185D6C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba00ca444a2425c2479cfd12d15d915737a0a2ad","datavalue":{"value":"optimal sequence alignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$EE9C4F48-6583-411F-B249-420F69B43EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a18008713d9b5af50f2673c8e031042ac78b83a4","datavalue":{"value":"comparing two biological sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$C93D213A-54C2-4074-8EAF-AF3E3990CBBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d81f9122504661af1b650e22ba37053c6f71ebb3","datavalue":{"value":"affine gap costs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$978BB56A-1C08-41C8-801E-42F30661215E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75a28749191141bc09b6c4adce68181b450ea061","datavalue":{"value":"path graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085098$4F16D5EF-EFA3-4223-9B62-EE1A47D80966","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"64d760d3898c61680503dfcb722b42761d8c0e88","datavalue":{"value":"Q56456148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085098$703502AB-E0D4-4767-91D1-0C83B51FD76C","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":"Q1085098$308BBF94-968D-43A2-BF4C-6E157C64343A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d379451811dcf86405ad19385e8727e8019a61f","datavalue":{"value":{"entity-type":"item","numeric-id":1085099,"id":"Q1085099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$EFC7A10F-E255-497B-B078-2C7A6A34FF8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e32ec80eebd452d3003a4cdaf9b4c61919b6700","datavalue":{"value":{"entity-type":"item","numeric-id":4042877,"id":"Q4042877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$09906AB7-1CC7-454D-AFCE-C92F54AE4925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f3a5cf7e6264ede0de1fae0eca03945757e6502","datavalue":{"value":{"entity-type":"item","numeric-id":1232251,"id":"Q1232251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$B079C843-08A2-4694-9AAE-6B3528434FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75a76e17cc8aa3c73582cc4d2ab28ad578e798ff","datavalue":{"value":{"entity-type":"item","numeric-id":3315039,"id":"Q3315039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085098$9FEC59C3-6BF0-43A3-964E-60C70D41E07C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44f9c4110a48879f59809b5402c17170b8481665","datavalue":{"value":{"entity-type":"item","numeric-id":912793,"id":"Q912793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39bbc1a68945363c0310f59a21b99a8c1d880878","datavalue":{"value":{"amount":"+0.8172036409378052","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":"Q1085098$8E3DA14F-58D2-48F8-98E9-35D3DE5E48C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80537dcef08fc1cdf9eabd4d67fab237d0abbefd","datavalue":{"value":{"entity-type":"item","numeric-id":3995867,"id":"Q3995867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79dfce3be5796a58d96c09f9984b147af05cea79","datavalue":{"value":{"amount":"+0.790252149105072","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":"Q1085098$2BCB45DD-76CD-4F42-8406-7AB0A0E16B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e723464ee3d7cd84770b7dc1a91f163b5e88816e","datavalue":{"value":{"entity-type":"item","numeric-id":3550840,"id":"Q3550840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9dcead5a98f3ebdc2b40d26877f31c3ae9d2b8f","datavalue":{"value":{"amount":"+0.7868507504463196","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":"Q1085098$24AABF94-33CF-434B-BD38-7938CA50983E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dca9930c25b27f8da61c391ccd398bba953e8dcf","datavalue":{"value":{"entity-type":"item","numeric-id":3139564,"id":"Q3139564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb5a3620972dcea5af09c74e0db1e6354d54283e","datavalue":{"value":{"amount":"+0.7753663063049316","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":"Q1085098$FFD316EE-C03B-4714-997F-3D0621903910","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":"fb5a3620972dcea5af09c74e0db1e6354d54283e","datavalue":{"value":{"amount":"+0.7753663063049316","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":"Q1085098$EBB71062-30B0-484F-AB0F-0568A329BA59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal sequence alignment using affine gap costs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_sequence_alignment_using_affine_gap_costs"}}}}}