{"entities":{"Q1894790":{"pageid":1905532,"ns":120,"title":"Item:Q1894790","lastrevid":73717563,"modified":"2026-04-14T17:01:30Z","type":"item","id":"Q1894790","labels":{"en":{"language":"en","value":"Multiple sequence comparison and consistency on multipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 778906"}},"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":"Q1894790$EDCB7C26-D36C-476B-A56C-3CCCBC7C2C32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66df4b01d1ca7bd8244780f0e08eceb130464bd7","datavalue":{"value":{"text":"Multiple sequence comparison and consistency on multipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894790$8F7CA785-B8C7-4696-A875-F5F6A17591F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f27490ea66b93d3050956f1d9aef46e00d57d055","datavalue":{"value":"0833.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$F5208374-663F-4F49-AC62-5521EB5D8EA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"324ee2a06b7a39200ab0fb3b3d26cfd43f019879","datavalue":{"value":{"entity-type":"item","numeric-id":242888,"id":"Q242888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894790$EB4299CF-38EF-488A-BB25-1852AC6417CA","rank":"normal"},{"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":"Q1894790$6BCF97F4-BF09-4E0B-8B14-946DD74EDBE3","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":"Q1894790$1706550C-5C90-4F8C-8D21-28BAF1BF60A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"894be799020e9aad5f698deaabf9e3b9c5d87e0e","datavalue":{"value":{"time":"+1996-03-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894790$7DA28340-E5DD-4CFF-9C07-42DAFD24DECC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d47099159705eff5a1af95d63c3dbbde3ce7e3df","datavalue":{"value":"The human genome project has generated vast amounts of biological sequence data. While pairwise comparison of such sequences is traditionally done using the so-called dot-matrices, multiple comparison of \\(n\\) sequences poses the challenging task of identifying commonalities or consensuses in these, using the pairwise comparisons. The authors model this as an \\(n\\)-dimensional image reconstruction problem. The pairwise comparisons may correspond to projections of `real' \\(n\\)- dimensional points or `noises'; that is which are not projections in 2- dimensional coordinate planes of \\(n\\)-dimensional points. One way for the reconstruction is to use a notion of consistency of the pairwise comparisons, and the other extreme is the idea of transitivity.   The mathematical model used is that of an \\(n\\)-partite graph \\(G(V_1\\cup V_2\\cup\\cdots \\cup V_n, E)\\), where the \\(V_i\\) correspond to the biological sequences consisting of `real points' and `noises' and the edges \\((i, j)\\), \\(i\\in V_s\\), \\(j\\in V_t\\) represent the pairwise alignments (dots). Consistency is defined through the membership of the edges in triangles. The mathematical consistency problem boils down to determining a maximal consistent subgraph of \\(G\\). Besides showing that an earlier algorithm by the first author and \\textit{P. Argos} [J. Mol. Biol. 218, 33-43 (1991)] may involve \\(O(L)\\) numbers of iterations, each of complexity \\(O(n^3 L^3)\\), where \\(L\\) is the length of the sequences, the present authors give an algorithm with overall complexity \\(O(n^3 L^3)\\). The transitivity problem is the dual to this and can be tackled similarly. But, what may be useful for biological applications, is the introduction of a hierarchy of consistency classes through the idea of \\(k\\)-consistency defined here by means of a `\\(k\\)-mask' of a matrix. The utility of this is illustrated by the study of the protein elongation factor \\(Tu\\) in drosophila, homo sapiens and ten other species. Three open problems are suggested.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$5C063ABA-95B5-472C-BA91-0FC80DB3D31F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$6640AB79-DCBB-4FA4-959D-3426AB6367A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$D4F41802-2B9B-452F-886C-E7D7E2F79186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$73E16BB1-4000-4256-A2F4-45FF3F3370E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$D9115292-B545-4AA9-8292-BCFF7AFE449E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505a49771a29a1df80db47f27f0ca3c9ddd29e48","datavalue":{"value":"92D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$61C6EECF-8F3F-4416-B39B-05A2CFABF33D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35a5583c36387374a8dc61af741c0b9534ed1def","datavalue":{"value":"778906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$AA652FCD-3F13-42F8-A52B-E4735D9C045E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbae876c1d9e4320757e1686e176f9c46336b170","datavalue":{"value":"multiple sequence comparison","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$04B387AE-928E-40B4-B9FF-8C61DD19582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"584b864cea23f60ab2b00e479e2b0588f3493156","datavalue":{"value":"multipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$1EE392AC-A661-40B6-9D28-4CE94582185C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cbd801e0382d1144886150fa5fc3cdfa460367f","datavalue":{"value":"biological sequence data","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$70AA365A-FE71-423D-A920-FC7573930ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45c80ebee5417e1ce1ca2627f86eff40dd1073c4","datavalue":{"value":"pairwise comparisons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$92D42F5E-2E83-4B70-AE2B-8845824973CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$9660DCFF-DB50-4706-BC66-B8C6163A5AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52c2513afc8941299b07e63a5555cd1e7cb85f4a","datavalue":{"value":"consistency","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$EAE332F4-D066-4F8A-8C72-D7E7065E1DEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49388e046339f86e6623a972cf68b5665500aba7","datavalue":{"value":"transitivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$1AC3596F-600E-41BC-B299-3AED165C0527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec357388f19d214c5eb4767c98277288e74f496","datavalue":{"value":"alignments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$B6B7E9C1-9801-4C84-8515-24F908AFE0BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$1AB4D099-2D84-412E-952E-41CF35B50E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$5ADEDB8B-6971-4329-9279-8B9F1A3914E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5385e12bb3ca4920ccbc9b28f631914eaa132b3","datavalue":{"value":"protein elongation factor \\(Tu\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894790$05B9541E-01F8-488B-BD07-69C65F73C3B1","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":"Q1894790$2819B64B-DBBA-4EAF-B1A3-FD15D49BD62D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1b93038bef9913740bb82202d7a12f77b84d548b","datavalue":{"value":"https://doi.org/10.1006/aama.1995.1001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1894790$23911017-09B1-415F-A3F3-B22AA35A50B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c62381292edbbd2e0327435873129e583d301290","datavalue":{"value":"W1999890519","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$CCE022A7-175E-4824-96AF-20E49C10D4AD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b604290c20607b868a6de9e517ceccba109cb960","datavalue":{"value":"10.1006/AAMA.1995.1001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894790$104C51B5-F2CA-433D-9E6D-9B294A211251","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"beaac18a94da9992dc2d820013cf533b7a9aa1b1","datavalue":{"value":{"entity-type":"item","numeric-id":912794,"id":"Q912794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6ffff2a24d5a987478dc10cbf762f0f55479405","datavalue":{"value":{"amount":"+0.7686397433280945","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":"Q1894790$C1929414-A347-4117-A6C8-7F614F0F2441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2887fbe0f6f8266894c8e39e8864b3023d445e7c","datavalue":{"value":{"entity-type":"item","numeric-id":3091376,"id":"Q3091376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af2ccdc1a7b70720ae779d6d6b4be1c278b64b85","datavalue":{"value":{"amount":"+0.749913215637207","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":"Q1894790$6121447C-2078-4908-A5FE-36376D989AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3aaaa94bd3508bdd544b0bc9cfeb81dc806de00e","datavalue":{"value":{"entity-type":"item","numeric-id":1059004,"id":"Q1059004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f3d5e61159986a5a43ce37591b93e56b061720a","datavalue":{"value":{"amount":"+0.7387884259223938","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":"Q1894790$C8414594-CDB1-47B9-88F3-B97C9C1C94A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dae28cc0d2614c147745d2e1b1d528a51fe0ec03","datavalue":{"value":{"entity-type":"item","numeric-id":5961633,"id":"Q5961633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"667fc0f69902a534a8332082a5b184f47756ec6e","datavalue":{"value":{"amount":"+0.7379017472267151","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":"Q1894790$2A65D053-5063-4F04-B0C5-BC17FE7D0047","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":"667fc0f69902a534a8332082a5b184f47756ec6e","datavalue":{"value":{"amount":"+0.7379017472267151","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":"Q1894790$C8DF1F08-621F-4607-B0E4-F2DEDDB5C674","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Multiple sequence comparison and consistency on multipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Multiple_sequence_comparison_and_consistency_on_multipartite_graphs"}}}}}