{"entities":{"Q5961633":{"pageid":8138435,"ns":120,"title":"Item:Q5961633","lastrevid":97752803,"modified":"2026-06-05T15:20:45Z","type":"item","id":"Q5961633","labels":{"en":{"language":"en","value":"Local multiple alignment via subgraph enumeration"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 981930"}},"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":"Q5961633$40941783-B66E-4EDF-9308-C0360AE2F162","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9bb5d0e59f79d1c462d3d4511a91372e0d8a6eda","datavalue":{"value":{"text":"Local multiple alignment via subgraph enumeration","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5961633$E35716E1-706C-493D-875C-B739F6913D8D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"878613bca29153be31deaffbbe091a04ca5f56f0","datavalue":{"value":"0899.92019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$8085BEEA-D8A5-42B2-95D0-0A1C252153AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"32baa22487622963ca621c144c3ebea0b62e6811","datavalue":{"value":"10.1016/S0166-218X(96)00072-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$0026B993-E349-410E-A363-8E0363E2E283","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$D0804ADB-BED6-44F6-A7E1-BCD5E76994AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"874b84f4e4c3d1120a3f15a09b668720ffcef7e9","datavalue":{"value":{"time":"+1998-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5961633$91A7491B-09F0-4E44-AE31-797172A85785","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q5961633$7CE9A8D5-0526-4BBC-8523-88D816DC41B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cc6a2d1a81aec0cb5abdfe44055f934ac25329b","datavalue":{"value":"92C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$7EBAB719-87F3-4C8E-9BAE-7DDD7C224A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$675BBE70-5775-4EF4-A051-445CEFF37DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$60EB63FB-FF91-42CC-BEF6-46615359E623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$1ECE068B-1FFD-451E-8A5C-BDB15BAEC96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$666E63AF-CBE0-4169-B8B8-D9A67E76A842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c061e4e7ae883786725eafc8628fcf7f3e822514","datavalue":{"value":"92-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$30A8B771-3142-4D85-8DDA-6292344EBB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d1f357130b885564de2a7f813fae2f00846119cd","datavalue":{"value":"92-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$2568FC9A-75C3-483F-9F2A-33D68B0AB904","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e68900be9abe1345a7758c672ad1a89216b4fdf","datavalue":{"value":"981930","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961633$848394E5-5AFF-4F65-B4F0-37FBFBAC1BF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8564c5ce94b9d47b73ab5cfbb41fd5a39144bb91","datavalue":{"value":"sequence comparison","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$C8332C75-828A-413E-99A7-6BD24FA5C15E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83c682103cf2e6224a201f16b11408889f832c5d","datavalue":{"value":"subgraph enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$07457235-F43A-4AC4-BF50-214F651252F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2520028a283b9491b30744fc9789184f43d7b56","datavalue":{"value":"maximal clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$35D47A5D-DEE1-4F20-A6FE-897E638D0559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8911ee593b62801522600f2197e153aafc44acf","datavalue":{"value":"molecular biology","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$E9F5A1D2-01F6-4BB8-B0FE-CA36AF5D0293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5ebc797a20b41b114bf017a4c468eb6accb676a","datavalue":{"value":"blocking","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$F8B38309-D875-4386-92D3-BD3C06ACF24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"722f5ce25eca9eeaee5e27a9c1341d8a420a6d5d","datavalue":{"value":"chaining","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$FCA2AD94-AF35-4530-9FF0-46B273CA3383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df65b51d33f5cfe57295030ea82dbf613a3d5165","datavalue":{"value":"flattening","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$A82A6E45-B95E-445A-BA13-0EA67C85EFE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"824e8483b5429e48606a64e90d96c4381f5a7ecb","datavalue":{"value":"multiple alignments","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$DCA7F1CC-312A-4414-B749-BBEF86F5FB6A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2effd94eb5a44fe4af2ea387194b949918acf490","datavalue":{"value":{"entity-type":"item","numeric-id":23950,"id":"Q23950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$EBD1E9A0-750A-49C4-9CAD-13D5FC834C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"0bd02c26dee295e17fa1661a740b0e3277993f7d","datavalue":{"value":{"entity-type":"item","numeric-id":37543,"id":"Q37543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$CFEBD155-889A-456C-BC95-BB547AA23583","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":"Q5961633$1B640736-4EBD-4809-A7A8-C0E87DDED9B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"078e0a5ec559210a14a4145be98e18a1a255f6b1","datavalue":{"value":{"entity-type":"item","numeric-id":5677064,"id":"Q5677064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$55719649-54CC-4F84-A636-ADC5BB3E3F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e5d605773d037db15b3bbc8a47095d81939df12","datavalue":{"value":{"entity-type":"item","numeric-id":1902469,"id":"Q1902469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$92D4A908-7896-41CE-9687-C8DEBFFCB689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$32D24DBE-0C22-49A3-82CB-C350E6C6EFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97a46f2a39d972713ad151c5d9b6dd197744b40f","datavalue":{"value":{"entity-type":"item","numeric-id":4302803,"id":"Q4302803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$E9BE5AC9-E049-4038-B31F-0956269C6145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$EAF964B9-BB4D-43D0-AFC9-6100DA1706BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fd0b57ecaa4d09d1c4310d93fe4bf1cf877c36f","datavalue":{"value":{"entity-type":"item","numeric-id":4282002,"id":"Q4282002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$D8C8F77D-9807-424E-8D9A-ACE964E32716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2493638b1f48cfa441d8f185fc09f25a954dc5e","datavalue":{"value":{"entity-type":"item","numeric-id":1203038,"id":"Q1203038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$B8B107D8-6B73-4EE7-8304-A16470B07A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$380D0B60-1581-4D13-9F34-670A2A47AFA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c77951f13339df5bd77b53cdd08d034b798b032","datavalue":{"value":{"entity-type":"item","numeric-id":1189709,"id":"Q1189709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$E4DB668A-EDCF-442E-AE47-1EC966C67A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ba7598a622756daa7a1a98c7ec39119480164a","datavalue":{"value":{"entity-type":"item","numeric-id":1108809,"id":"Q1108809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$CF9F7C6E-8D64-4A09-A5CA-17386D455A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cee622c8004588ce4ee327462c9cddb2144c21dd","datavalue":{"value":{"entity-type":"item","numeric-id":3890128,"id":"Q3890128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$FF806788-3993-429F-9581-FD02E150DF6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef934452df2f09c58731f9b314e1a804874b9eb","datavalue":{"value":{"entity-type":"item","numeric-id":4886031,"id":"Q4886031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$9625FC4B-18B5-4E57-8966-A15D13D22DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb85e2a08b123210f7ea1cf8a8c1c958121dd184","datavalue":{"value":{"entity-type":"item","numeric-id":4138754,"id":"Q4138754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$D9C505B4-D211-4F42-BF66-FA40DA7DF6ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e430e6f16c180702fcd496b9e1c29095f34480d","datavalue":{"value":{"entity-type":"item","numeric-id":1894790,"id":"Q1894790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$4C7A8003-D872-4586-8AAE-8473B9936090","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c4e09b7ed747246bd2458f912a298dcccc5c395","datavalue":{"value":{"entity-type":"item","numeric-id":4037677,"id":"Q4037677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26cad1f751ca593493965bca832d36ab51dd65b1","datavalue":{"value":{"amount":"+0.86371785","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$4C0E110F-CAFA-40B4-84EA-65CDC90A2F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ed0e6a3d536ec76d189b00c8b20e60eca4d0bda","datavalue":{"value":{"entity-type":"item","numeric-id":1993381,"id":"Q1993381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9b2328fb16c4df85daf07a19d04eca7fa0fc150","datavalue":{"value":{"amount":"+0.862387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$5C3B1715-05AA-4B42-8713-9A3042D6BF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1d09557d03fea943aa7add75586e79b63ebc401","datavalue":{"value":{"entity-type":"item","numeric-id":5159214,"id":"Q5159214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6670477d1c6099836cb43461fc02fe922d57aa8e","datavalue":{"value":{"amount":"+0.8532479","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$02244C12-45DB-4723-BE66-53A5E31A644B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6198c042388cf06aacf836f6a42bcd72729b60c8","datavalue":{"value":{"entity-type":"item","numeric-id":2415245,"id":"Q2415245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51c622abadae2c4cfd6a2970750e2afe80bdc0ac","datavalue":{"value":{"amount":"+0.84821767","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$D11AFC02-CCF3-4457-BD9F-62A531FFD2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f65883cdaa05c737e8587648ff1f996d45d16029","datavalue":{"value":{"entity-type":"item","numeric-id":5293351,"id":"Q5293351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e3cded5763f9bde2fdf78042d05d161fad435dc","datavalue":{"value":{"amount":"+0.84795046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$723519C8-D2F8-41CF-963B-98511A7D1917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"200963f6ae48b8bc470ed5f0426269757cb50f8f","datavalue":{"value":{"entity-type":"item","numeric-id":5491601,"id":"Q5491601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc67576aeed76f1864a5aa33e7e27fad0e2d9d6c","datavalue":{"value":{"amount":"+0.84230185","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$4ACFCACE-8540-4ACC-A812-F7A8C87F56DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"139692237d3061538d92e04f5e21d3481d38717d","datavalue":{"value":{"entity-type":"item","numeric-id":5507036,"id":"Q5507036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8587eb968038221591c5774eb5af37e0b3af71ce","datavalue":{"value":{"amount":"+0.84205693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$05912C31-4B5C-4FD7-B800-317403E52101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1d530efcf9db720eea20178779e3fb5f257491f","datavalue":{"value":{"entity-type":"item","numeric-id":3044314,"id":"Q3044314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4fa80deb5d4f14e4092c82a8db3dba906ed033b","datavalue":{"value":{"amount":"+0.84197116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5961633$7B8669D5-BBB1-48E7-9217-0ADA96D8D993","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"37633849a4379dd9a418c1e8589567496f8ec8b4","datavalue":{"value":"The algorithms described in this paper were developed to solve the following sort of computational problem from molecular biology. Suppose a newly sequenced protein has been used as the query for a database search, and that statistically significant similarity has been found to, say, six sequences from the database. The problem now is to identify the motif or motifs that are common to most or all of the seven sequences. In particular, the following difficulties may arise. (1) A motif may not appear in all of the sequences. (2) Two distinct motifs may appear in different subsets of the sequences. (3) A motif may have multiple appearance in a sequence. (4) Two motifs may appear in different multiplicites and relative orders in two sequences. Moreover, as in most sequence analysis problems in biology, when we say that a motif appears in some sequences, we mean that there are substrings that approximately match in a sense that needs to be made precise. Finally, the alignment-scoring scheme most appropriate for providing the desired precision to the notion of ``approximately match'' may depend on both the set of sequences and the particular motif.NEWLINENEWLINENEWLINEWe discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a ``block'', from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961633$A59CBB61-1D87-4A5C-9A04-E30415363EF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97b3384e8839d7520f8d7ce54f3495f0551091fb","datavalue":{"value":{"entity-type":"item","numeric-id":6770765,"id":"Q6770765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$12C06701-5A65-4F92-9411-525BCD8367BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25db230f4ae4138df5c781b95ed96a9157285abf","datavalue":{"value":{"entity-type":"item","numeric-id":6126615,"id":"Q6126615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$3FCC03EA-F8D2-41C7-A168-3624F3D79AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"be6807a0bf66a33268005bd1b0e680c44d587816","datavalue":{"value":{"entity-type":"item","numeric-id":6455735,"id":"Q6455735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961633$5E94B678-DE22-44FE-8024-CFAAF953CEBE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Local multiple alignment via subgraph enumeration","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Local_multiple_alignment_via_subgraph_enumeration"}}}}}