{"entities":{"Q1736589":{"pageid":1747330,"ns":120,"title":"Item:Q1736589","lastrevid":72381246,"modified":"2026-04-14T04:31:17Z","type":"item","id":"Q1736589","labels":{"en":{"language":"en","value":"Sublinear time motif discovery from multiple sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042182"}},"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":"Q1736589$4ED25D51-67D9-45CA-87B1-2189210FD9B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3459121966638ed81a683ead89c3b172dbaa8cfc","datavalue":{"value":{"text":"Sublinear time motif discovery from multiple sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736589$FA145844-968D-4CB6-A7FB-C5997169A821","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0380ca4775cce4a589a578178aeede811c1d200e","datavalue":{"value":"1461.68265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$32F17CCA-AD1C-4FB1-BC27-5020CB451F7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d224193872547e7ed5c8874bbaf20d2bd49220bb","datavalue":{"value":{"entity-type":"item","numeric-id":313968,"id":"Q313968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$CC064F15-BEE5-48B8-894B-078C92F942A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c87f27c86ef6bc6f55a0ccc10d0e08bb5984f113","datavalue":{"value":{"entity-type":"item","numeric-id":1736588,"id":"Q1736588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$02778CFF-74EE-4355-A4AE-9A5658D43E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1221185e01145cda40db8ee99467e6b25258cd6d","datavalue":{"value":{"entity-type":"item","numeric-id":526820,"id":"Q526820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$9F52AF35-E489-441E-A9FC-49F56724DB16","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$DC1209BC-4590-4C90-AB92-0E923492D65C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736589$6A442AB7-3212-4F91-A395-5BCA90A14ECA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"afceea8b68dbd37b0a67f0001a2cdb593b3d114d","datavalue":{"value":"https://arxiv.org/abs/1007.2618","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736589$94ABF824-338F-4DFC-8F4A-03CE9F1C941D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18df859fa454dff14ab5a2d2c4d998e5ad125df6","datavalue":{"value":"Summary: In this paper, a natural probabilistic model for motif discovery has been used to experimentally test the quality of motif discovery programs. In this model, there are \\(k\\) background sequences, and each character in a background sequence is a random character from an alphabet, \\(\\Sigma\\). A motif \\(G=g_1 g_2 \\dots g_m\\) is a string of \\(m\\) characters. In each background sequence is implanted a probabilistically-generated approximate copy of \\(G\\). For a probabilistically-generated approximate copy \\(b_1 b_2 \\dots b_m\\) of \\(G\\), every character, \\(b_i\\), is probabilistically generated, such that the probability for \\(b_i \\neq g_i\\) is at most \\(\\alpha\\). We develop two new randomized algorithms and one new deterministic algorithm. They make advancements in the following aspects: (1) The algorithms are much faster than those before. Our algorithms can even run in sublinear time. (2) They can handle any motif pattern. (3) The restriction for the alphabet size is a lower bound of four. This gives them potential applications in practical problems, since gene sequences have an alphabet size of four. (4) All algorithms have rigorous proofs about their performances. The methods developed in this paper have been used in the software implementation. We observed some encouraging results that show improved performance for motif detection compared with other software.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736589$9B52679B-74C1-4E88-9419-CB803D3703E1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$581411C0-F1BB-4965-BC85-DC34AC4863FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$6A47443D-37F4-41BE-BA90-AF5B9E2C2528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c061e4e7ae883786725eafc8628fcf7f3e822514","datavalue":{"value":"92-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$B036325E-CAC5-4C4E-8C78-323BA73A0FAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505a49771a29a1df80db47f27f0ca3c9ddd29e48","datavalue":{"value":"92D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$CF2BAD52-E559-4FD7-A4E1-48BDA73B296D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"971383bcda500c0b98d3e1258f50e57995a80d42","datavalue":{"value":"7042182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$B772EAD6-DAFF-49BE-AD06-E00B30683F4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3eb10533df708be966b7c2d7af840857189b5027","datavalue":{"value":"motif discovery","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736589$AD0F7B94-9D37-4AB9-A45E-50AA6D86D154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e225edfcfee3bc5b9c506e1bad6a172e676dfa3","datavalue":{"value":"sublinear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736589$F8D9E06B-F5C3-41D3-AF53-ED20CCE4F127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736589$2626F10E-4307-4B62-8A91-1821DB0B1CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"610a630ffab00b7233f7e3ba00b63a0c5e848bea","datavalue":{"value":"deterministic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736589$DF4FFB89-18E5-439C-9ADE-72FC75BDE495","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"9a94fd798bc6468c46fb1bca4df80c5ebd1d02a7","datavalue":{"value":{"entity-type":"item","numeric-id":47230,"id":"Q47230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$FAE0B020-B0FB-4A5E-B27E-D07DA25D5097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b0b1ea0bde1d12c4973da2c78c1fa09d4c7a0670","datavalue":{"value":{"entity-type":"item","numeric-id":51347,"id":"Q51347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$BFE74E16-7F86-493F-B6B3-CDD7409157DA","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":"Q1736589$CED10830-04D9-4B80-B6A3-A3800D40187F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"380db3c968637edf6709a0a7d0ed4f3c33c2c894","datavalue":{"value":"W1999959196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$1969F2C9-6C13-4131-88A1-70712EDC0269","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a32f9eb182c7461392b0c1bec9e662087c05f8f","datavalue":{"value":{"entity-type":"item","numeric-id":675858,"id":"Q675858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$6A913B8B-031C-42C2-9E32-594858AAC37F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19ca18395bbca9a06db424721c49e7767fa70d2d","datavalue":{"value":{"entity-type":"item","numeric-id":4252402,"id":"Q4252402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$FDDDC002-3F41-4C6F-9784-94DD711DC574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df92bd73445dbe3246228a0018de5d5dd067d1a1","datavalue":{"value":{"entity-type":"item","numeric-id":1427861,"id":"Q1427861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$5E8B65C8-E959-4B13-96D0-18A1F2A3B7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02901919df95c5cfee893a7b08627856779e1e47","datavalue":{"value":{"entity-type":"item","numeric-id":3196639,"id":"Q3196639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$D5B4FF5F-BB5E-4A80-A287-137E77FDDABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef97d1431b7fd61c2f7b8f04d4fba63961aaa07","datavalue":{"value":{"entity-type":"item","numeric-id":2819580,"id":"Q2819580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$874F1467-11C7-4CC3-A586-C84CD7EF3A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$0084A378-A14E-495E-AC9A-9FA7EFCBECBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072968eb16dccb56546059dd391d5ed9e36080a1","datavalue":{"value":{"entity-type":"item","numeric-id":3058527,"id":"Q3058527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$ED45E53B-549E-4B80-B4FE-5C4AC0D75CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd61ffe2ae4a48bda9c034fc969db5ff2e852b1b","datavalue":{"value":{"entity-type":"item","numeric-id":3189008,"id":"Q3189008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$C4ED5329-4779-46CA-A973-BBFBF95D064B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d05652188e444fc35e748b68b983451566933e27","datavalue":{"value":{"entity-type":"item","numeric-id":4856179,"id":"Q4856179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$4CE3B09D-809E-4111-9F80-BE64CFCB6B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f07818b634e459fdfbede08defa40c8e8ef26894","datavalue":{"value":{"entity-type":"item","numeric-id":4139463,"id":"Q4139463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$DD9CD610-A8F1-4E2E-B795-EABAC7A12551","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e70f892b1839a2370d53c0483d97641fc8c77ba","datavalue":{"value":"10.3390/A6040636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736589$12FAE57C-D65F-4B03-B14F-1E83961D0D11","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c27d4b1f05995952a0c3347087a8089494901c0","datavalue":{"value":{"entity-type":"item","numeric-id":3630208,"id":"Q3630208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"680b9e4762dec77238b1d05f3ce110e6c8929320","datavalue":{"value":{"amount":"+0.8965234160423279","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":"Q1736589$7BC47A96-0308-484D-ACEC-17B32E2F1971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aea8115cb3d5a3dea7f9a617dd38dead85358250","datavalue":{"value":{"entity-type":"item","numeric-id":3502650,"id":"Q3502650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f76e4024cd3d7ae405b0c93a5d881b3f6f5ff74b","datavalue":{"value":{"amount":"+0.8964626789093018","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":"Q1736589$F0DA551B-E1E4-419B-8E41-EE0F1CB9A53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5059d07aeb6b221b5292e16c258f6b701423aaf3","datavalue":{"value":{"entity-type":"item","numeric-id":3189008,"id":"Q3189008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72bd2062a86f2f82850e6f18008e3bb2fed04510","datavalue":{"value":{"amount":"+0.8920886516571045","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":"Q1736589$FABE0863-9B20-45E3-BC63-B8E7889464B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05a23031158076f01df30347f16556697559694e","datavalue":{"value":{"entity-type":"item","numeric-id":3058527,"id":"Q3058527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f206073852395e41584b943b122990b9a9250225","datavalue":{"value":{"amount":"+0.8851639032363892","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":"Q1736589$E20F9E1B-3408-4301-AF69-792777EDDBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9a77e18a9c41fb48f289f3b203cde0044a27fbb","datavalue":{"value":{"entity-type":"item","numeric-id":5712174,"id":"Q5712174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44894712fb0277bc85d3270a6bf51325171249b5","datavalue":{"value":{"amount":"+0.821086585521698","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":"Q1736589$5F6FB0D7-2027-4328-9528-6C10ABDAE8F6","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736589$BCF1C7B1-BE2C-46AA-AE24-4DEAD93E62FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sublinear time motif discovery from multiple sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sublinear_time_motif_discovery_from_multiple_sequences"}}}}}