{"entities":{"Q2326388":{"pageid":2337131,"ns":120,"title":"Item:Q2326388","lastrevid":53555765,"modified":"2026-01-25T06:51:30Z","type":"item","id":"Q2326388","labels":{"en":{"language":"en","value":"On overabundant words and their application to biological sequence analysis"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7114316"}},"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":"Q2326388$28A1D1EF-E797-4C07-BF7F-CB5C7D42E978","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"47ec07dab4f9412828c8a4af16b31775a465ce00","datavalue":{"value":{"text":"On overabundant words and their application to biological sequence analysis","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2326388$AFE899A6-5491-447B-A8FA-45E6255C4C2B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4539d00e340dc6739b822fca078a139c30223e74","datavalue":{"value":"1433.92031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$F2F25638-C3D1-4643-8DA3-F296EA7CE213","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d9cdae6f002594b7487e594aec5694eb290e07a","datavalue":{"value":{"entity-type":"item","numeric-id":1642717,"id":"Q1642717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$427D29C5-8B04-4D1D-952A-737E3815D4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"598bc1c70733a847259405a88f6606690d39f11a","datavalue":{"value":{"entity-type":"item","numeric-id":336290,"id":"Q336290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$88B5E1DE-3DAC-4E5E-B892-27E0100DDF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"57e626f6eafdef1fadc0325a4afbde0c9e282d56","datavalue":{"value":{"entity-type":"item","numeric-id":200907,"id":"Q200907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$9B0C3981-7BC2-4424-9F33-1572EB4DE9D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0edffbbd65205d6eb3204f5b56c983092a75770","datavalue":{"value":{"entity-type":"item","numeric-id":507404,"id":"Q507404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$822D2576-56ED-4C13-82A5-44FB4890437D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"299132b318bdfaa1a1b283f6513262778e0687d2","datavalue":{"value":{"entity-type":"item","numeric-id":294953,"id":"Q294953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$44B220DC-9AAD-446E-9DC2-891515F44B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c789d04f98fcc31486d1a0992aa1df14214f9eea","datavalue":{"value":{"entity-type":"item","numeric-id":1708406,"id":"Q1708406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$4EF15E6A-E37E-47AE-92F9-A63E626BE745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"056bfd09815f1ee19fc2fff89ac3c5c0ba9d743d","datavalue":{"value":{"entity-type":"item","numeric-id":1370216,"id":"Q1370216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$529C7C8B-7279-4356-97D2-699EC17A7F91","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$7BB93D46-E7A6-4C07-92E7-8CAD0993A003","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0027e7c78970709c142f5f04013afe779ba5e86b","datavalue":{"value":{"time":"+2019-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2326388$F552D964-B13A-465B-9FBE-776EAF426459","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"09493a2f38948b3ac36d9c3f488c46116f7c5827","datavalue":{"value":"https://kclpure.kcl.ac.uk/portal/en/publications/on-overabundant-words-and-their-application-to-biological-sequence-analysis(ec2b4dfd-49cb-4be3-bc3d-7cc48325339e).html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2326388$F33897E6-450F-498B-974A-63048FDFC886","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09b7f083f87b9cac75c3be5939b33d3767748110","datavalue":{"value":"The authors use the biologically justified model introduced by \\textit{V. Brendel} et al. [``Linguistics of nucleotide sequences: morphology and comparison of vocabularies'', J. Biomol. Struct. Dyn. 4, No. 1, 11--21 (1986; \\url{doi:10.1080/07391102.1986.10507643})]. They prove non-trivial combinatorial properties and establish that it admits efficient computation for overabundant words as well. The results in this article extend their former study by presenting an \\(O(n)\\)-time and \\(O(n)\\)-space algorithm for computing all overabundant words in a sequence \\(x\\) of length \\(n\\) over an integer alphabet. They also present experimental results, using both synthetic and real data, which further highlight the effectiveness of this model. The computational problem can be described as follows. Given a sequence \\(x\\) of length \\(n\\) and a real number \\(\\rho >0\\), compute the set of \\(\\rho\\)-overabundant words, i.e., all words w for which \\(dev( w)\\ge \\rho\\), by presenting an \\(O(n)\\)-time and \\(O(n)\\)-space algorithm for computing all \\(\\rho\\)-overabundant words (of any length) in a sequence \\(x\\) of length \\(n\\) over an integer alphabet. This result is based on a combinatorial property of the suffix tree \\(T\\) of \\(x\\) that are proved here: the number of distinct factors of \\(x\\) whose longest infix is the label of an explicit node of \\(T\\) is no more than \\(3n-4\\). Further is demonstrated that the presented algorithm is time-optimal by proving that \\(O(n)\\) is a tight upper bound for the number of \\(\\rho\\)-overabundant words.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$CB69CFE6-6A4F-4008-96A1-994A3025CDF9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fd03dca3d1429368d18ffad44410068392bf293a","datavalue":{"value":{"entity-type":"item","numeric-id":274762,"id":"Q274762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$176BCBED-26BE-4C01-AD29-164844B59067","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"505a49771a29a1df80db47f27f0ca3c9ddd29e48","datavalue":{"value":"92D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$BA99038D-A947-445A-8F4F-4F50E189FF69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3b0a22587432575dd8ab8708980328a5eeb487a8","datavalue":{"value":"91F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$7DB2259E-4C01-4DDB-BF92-A88C9F21553E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35f107b5143c9af4dfcb9cc811858dc33e394135","datavalue":{"value":"7114316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$89A141E3-0E42-4AE4-B382-F136B4EF9DE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08665286a4668e2e5abde9054a2a92a29516a3a","datavalue":{"value":"overabundant words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$A54FCE91-BEB6-4440-86BD-FB80A5B0C0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8d103f9f6660404d1de3db18fb78c48499f9496","datavalue":{"value":"avoided words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$4517F7A7-E65B-49EA-B823-FA30E4B7CDAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2450e02f50939b46b52c3140c8d1d485cebe36e5","datavalue":{"value":"pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$7B4F8905-C3EA-41B6-98B0-2E9828BF35B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d9a3b3d8e31d2bd3ef4b7ebcac2bdf4b0710820","datavalue":{"value":"suffix tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$EFBB5F25-9BAB-4E17-B671-B70DD2D62D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2da453cc30fc60e82a9057a87413f7b4c52e9b9d","datavalue":{"value":"DNA sequence analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2326388$22D417C7-C642-4B72-AC76-610672695458","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":"Q2326388$A0165754-09DB-4FE3-8B9E-1AAAF7916723","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6b79edac2ccf40d4b54f8ff38d55a585ee589427","datavalue":{"value":"W2892128519","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$BAC7DDD1-5E9C-4E18-BCFA-5487ACA95391","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"328078572de2409b3771b190873896b50dffcd8c","datavalue":{"value":{"entity-type":"item","numeric-id":5111793,"id":"Q5111793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$4265EC9B-2C6D-4003-820E-F1F5C05D7BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"990065e7b5851366e70c60b514bcd5c9a7dfca64","datavalue":{"value":{"entity-type":"item","numeric-id":4801141,"id":"Q4801141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$33B66B18-6268-48D0-85A2-C32CF1F94887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc3b2866ce6ec71c4cb34d8740b1e07292352416","datavalue":{"value":{"entity-type":"item","numeric-id":5444160,"id":"Q5444160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$FEAE1315-EADD-47EB-850C-5F628791856F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"590f321285074e3ca978723231274a99cd379395","datavalue":{"value":{"entity-type":"item","numeric-id":293331,"id":"Q293331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$172F55AC-5EB4-41F6-BB5B-FC67BA22EEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba8c4a329e1b75286cc59c394778594902b6f9ec","datavalue":{"value":{"entity-type":"item","numeric-id":1605329,"id":"Q1605329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$4978F848-E743-4417-BFD8-666E80768CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5262acdef5ab5c226bd34bafb2af823d2460adc7","datavalue":{"value":{"entity-type":"item","numeric-id":507796,"id":"Q507796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2326388$74F884C7-9B23-4378-8B33-E0156AF38491","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":"Q2326388$FA7BB23D-21D5-44D4-B65C-A7943097F725","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"456d7cfadae17bfcfc041bec2bd4273188eb3fec","datavalue":{"value":"10.1016/J.TCS.2018.09.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2326388$9C5598AE-BB06-49E5-A70F-8168E64D958D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef168dfc072bb87ef8480f1451a9165eae9c9433","datavalue":{"value":{"entity-type":"item","numeric-id":5111793,"id":"Q5111793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b9cc7095dbe9576ba2e383779f99b429a70e22","datavalue":{"value":{"amount":"+0.9720050692558287","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":"Q2326388$CC9D1519-EEE1-423D-B3D0-C743442D7061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec651fdab1f315b1b98a7381d5b6902a1ea711dc","datavalue":{"value":{"entity-type":"item","numeric-id":1708407,"id":"Q1708407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4acb5e8601e2a8248934625d25dd9fc44ece6a99","datavalue":{"value":{"amount":"+0.7772027254104614","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":"Q2326388$8C88EF52-776B-4B41-83D6-6E52DF5312D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40cc6a8623fdd3db73379db60bb94e3bc27ec7fa","datavalue":{"value":{"entity-type":"item","numeric-id":4020357,"id":"Q4020357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d25873de7990376293b1c75a74f4ce79b84ca28a","datavalue":{"value":{"amount":"+0.6913591623306274","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":"Q2326388$6539B5A8-7D83-42F1-AE96-655E17D4363E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"822b808d1ee07d419832e22eaad69695dfa47dd6","datavalue":{"value":{"entity-type":"item","numeric-id":2802951,"id":"Q2802951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6d4d69de9fc179b92d042fbb22d9873a82c46a0","datavalue":{"value":{"amount":"+0.6872959733009338","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":"Q2326388$C34EBE2F-AB0E-40A2-85A6-781F6E0993C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e8d54147c8d7d7160094116baba9eb6d67cd096","datavalue":{"value":{"entity-type":"item","numeric-id":1784946,"id":"Q1784946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f27234d1479f63d5ab9334761cd3becd49ecc1a1","datavalue":{"value":{"amount":"+0.6872050166130066","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":"Q2326388$8A2E324A-CA23-4BC3-8E36-43FC45A9A568","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2326388","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2326388"}}}}}