{"entities":{"Q2633234":{"pageid":2643977,"ns":120,"title":"Item:Q2633234","lastrevid":79319900,"modified":"2026-05-06T13:38:49Z","type":"item","id":"Q2633234","labels":{"en":{"language":"en","value":"Analytic combinatorics for computing seeding probabilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7052081"}},"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":"Q2633234$55F3F0EB-48C3-42A9-82AC-3E4D6D0CF6C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c8d71533f5da39ee9abcf5c2f240465946d6cc9","datavalue":{"value":{"text":"Analytic combinatorics for computing seeding probabilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2633234$783756C9-527B-4977-9B7A-7A6018F5E371","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"484b9c34c3cb7eef37d09f1c1bba75b95d61652e","datavalue":{"value":"1461.05006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$8510341E-6F4D-4A4E-A93A-45B65F8C1F7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c63502ec63667b877b29fbca561a3ceea8c2149f","datavalue":{"value":{"entity-type":"item","numeric-id":2633233,"id":"Q2633233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$B0D2B450-3584-4265-B56F-5AB690509F39","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":"Q2633234$45D3AA25-20BD-4066-A4DA-5E66A8469731","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8721ec9cf8de43034be561afa7e535bafe3c2e57","datavalue":{"value":{"time":"+2019-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2633234$E82DB446-ADE7-4075-9F60-F7068CC49B1D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb3b308aea21ec41860e8fdbb2645c96939efa9b","datavalue":{"value":"Summary: Seeding heuristics are the most widely used strategies to speed up sequence alignment in bioinformatics. Such strategies are most successful if they are calibrated, so that the speed-versus-accuracy trade-off can be properly tuned. In the widely used case of read mapping, it has been so far impossible to predict the success rate of competing seeding strategies for lack of a theoretical framework. Here, we present an approach to estimate such quantities based on the theory of analytic combinatorics. The strategy is to specify a combinatorial construction of reads where the seeding heuristic fails, translate this specification into a generating function using formal rules, and finally extract the probabilities of interest from the singularities of the generating function. The generating function can also be used to set up a simple recurrence to compute the probabilities with greater precision. We use this approach to construct simple estimators of the success rate of the seeding heuristic under different types of sequencing errors, and we show that the estimates are accurate in practical situations. More generally, this work shows novel strategies based on analytic combinatorics to compute probabilities of interest in bioinformatics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633234$549606BB-1A81-4AF7-8B0E-BB63DFA57D80","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$2F78783C-FF61-404B-978F-5782E7DA09AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$E56B3951-B15A-4807-94EC-D4458B066D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$C8DE60FC-FECC-4427-8D78-3718035BC42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4db22146753f5305670e78aa06ee0367ddbad55b","datavalue":{"value":"92B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$690D4BB7-30BF-40CB-B955-EAB8CAE1B99C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51700cb560c67023a3e758ba340150a82108311f","datavalue":{"value":"7052081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$613CE37A-A5AA-43B0-A6D3-EBD2F2BC0D2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c130d4d8ba196b05e16ed90a178ca34dcbfa704f","datavalue":{"value":"analytic combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633234$FEB2E1E4-BFBC-490E-9FD9-B2898242FBAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387d3da80700813b0b7691a140fd19c167fc00b3","datavalue":{"value":"bioinformatics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633234$8DF6F44C-9B9A-4B47-A38B-D6D67FB0AC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"868c9b4ce51da5df72d37dd76f2fedac5973ea41","datavalue":{"value":"seeding sequence alignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633234$63BF600E-3559-4249-95FB-AA569595AA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"931fc00879af8b0f86011ef32c390fa4802ca84e","datavalue":{"value":"generating functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633234$68C8BE3E-6B1B-4C98-B782-21BF8D30F984","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2827fb7a065e8dcc5b330eca3ed9bd689043a40a","datavalue":{"value":{"entity-type":"item","numeric-id":26418,"id":"Q26418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$333DA53D-9A6E-436D-B7B6-FF3B3914AB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b2f45492d0a9ee38c7f6f7ea29a7881599069d9b","datavalue":{"value":{"entity-type":"item","numeric-id":13519,"id":"Q13519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$F33843B7-86CA-414B-894F-BEBFA1A1892A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"61df89f9d35f054c611ce677d7e3a7adc537f0d4","datavalue":{"value":{"entity-type":"item","numeric-id":26264,"id":"Q26264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$1D2C3253-11C6-4906-A6C2-76DB5F0784F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"f8b544cb5956ed5f03f31c97b4b9c8838c926af4","datavalue":{"value":{"entity-type":"item","numeric-id":46083,"id":"Q46083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$E9273873-0186-42B2-A168-DAE63D1D4FF6","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":"Q2633234$DCFDEAB6-2EB7-43DB-B1FE-FFB459F8BB29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2189c5fd412a183bbb409df2b55b353023bc2c18","datavalue":{"value":"https://doi.org/10.3390/a11010003","type":"string"},"datatype":"url"},"type":"statement","id":"Q2633234$EC165E7B-751B-435F-A335-E5F3236D09B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7feb4c4927b6e1e3e3f6adf64dadaac7e438f7a7","datavalue":{"value":"W2782701038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$92B72AA9-AEED-44AA-A420-C8B774E93B64","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c7daef6bcfec4a523dde8517efb22e2b20b172","datavalue":{"value":{"entity-type":"item","numeric-id":4223050,"id":"Q4223050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$888D35FA-711C-4924-BF63-EDB13AD46F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36fd43cb37ce851103cbc12e152e4369e569a1d0","datavalue":{"value":{"entity-type":"item","numeric-id":3471897,"id":"Q3471897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$91DA8046-A7E2-4FCC-8B04-17B7229221F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76988eeb330b74201f9a4ad033a0fa0935f14c68","datavalue":{"value":{"entity-type":"item","numeric-id":3496337,"id":"Q3496337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$4BDA960A-95AE-40FD-BDE5-647BBAF0DA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e7ce1f5ce7b22cd65f95bcce844b0844c2e79d2","datavalue":{"value":{"entity-type":"item","numeric-id":4855565,"id":"Q4855565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$2761FE8C-F383-4487-9222-C8171B14C3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ef8fac80d379bd80260f843138869332bd9384","datavalue":{"value":{"entity-type":"item","numeric-id":3549563,"id":"Q3549563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$D9352D70-83AD-4484-9D55-9033461A89BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5cbae2f30502b5f150485e81fdf89a6d36422e2","datavalue":{"value":{"entity-type":"item","numeric-id":938109,"id":"Q938109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$1F2E3D84-2FB8-4726-85E3-F868148F4B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d47c57b1cdd66672dc64bc0c04399eab032f403","datavalue":{"value":{"entity-type":"item","numeric-id":4314909,"id":"Q4314909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$91E6DC26-2ECB-4B0A-ABC7-9D89D5CEA1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30c76db9c2cf9a095c204865753a6efd6ba3cb94","datavalue":{"value":{"entity-type":"item","numeric-id":3084794,"id":"Q3084794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$D39B6FD4-4B76-4969-A274-B761492CE800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4380e6329d2e0866413d52a27fe328bd8401682e","datavalue":{"value":{"entity-type":"item","numeric-id":5459921,"id":"Q5459921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$14FDA48E-F2D0-4BDB-AC69-FA1995689ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c14d536c84143066152134658a3dd85dad6445","datavalue":{"value":{"entity-type":"item","numeric-id":2787276,"id":"Q2787276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$EA35D6A9-A519-4C57-8023-A2E20427DD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12f1ee1dee5bb965dec7da3b02fbdecff91a1fc0","datavalue":{"value":{"entity-type":"item","numeric-id":1167168,"id":"Q1167168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$AB3B6EA7-4EB1-4481-AB7B-C7377D8FF818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aed92f70f867050a2d0ef53846b7f4ea152152d","datavalue":{"value":{"entity-type":"item","numeric-id":5172950,"id":"Q5172950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$EAB8618D-D853-41A8-B86E-0D1D55823464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb8d6afcc0f2ec7b0126ec742aaccdeccbec8244","datavalue":{"value":{"entity-type":"item","numeric-id":1201808,"id":"Q1201808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$8F4916A1-9212-43F8-9DB7-747FE81C2045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c40d56e6790ebfebb8e4a2285c5c9cb31acd3ee","datavalue":{"value":{"entity-type":"item","numeric-id":2856004,"id":"Q2856004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$0621C070-8FA5-44FA-B0EA-44426561CE27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a90c73bcf65723c5caa489891ceb2b9a228fc41","datavalue":{"value":{"entity-type":"item","numeric-id":4046051,"id":"Q4046051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633234$4B1478A7-E8D6-4206-A47A-E31D91B60FAE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0881d09a524b0dc87335a9ff378ac0aa0721bab1","datavalue":{"value":"10.3390/A11010003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633234$F9813C45-4C9D-4D3D-9250-668EE0F694F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21708f112c2a96d656756e770f5b4673d3ea0bec","datavalue":{"value":{"entity-type":"item","numeric-id":2643726,"id":"Q2643726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11c35849b6e31451f62311f29c421e80201fa56d","datavalue":{"value":{"amount":"+0.7019157409667969","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":"Q2633234$62DBC90B-1FEF-478A-A82B-D30BE53957F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3927c9c7513068b31670ceb69382aa20b1d1afb3","datavalue":{"value":{"entity-type":"item","numeric-id":1827801,"id":"Q1827801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2da64883dc9a832f73c9c6aea5afd268b9ed251d","datavalue":{"value":{"amount":"+0.6930760145187378","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":"Q2633234$35CC822C-1B40-4CF7-84FD-3A57DFA5EEC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2329df9462c32267b11d0518e1e20ded79199a84","datavalue":{"value":{"entity-type":"item","numeric-id":3612577,"id":"Q3612577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a798a11b9b3dff552d9dc44ca2f40617fe89b835","datavalue":{"value":{"amount":"+0.6770163774490356","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":"Q2633234$FCD89941-E0F5-43DB-9BA5-531731882C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5fb55bec3a4560c7668a8b6bae5cb5665f15fe5","datavalue":{"value":{"entity-type":"item","numeric-id":1878677,"id":"Q1878677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1e55259b31bf96c30e6877b35ce101fe5667e72","datavalue":{"value":{"amount":"+0.6681154370307922","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":"Q2633234$49EB67A4-0BF2-4410-BDC0-A6E421454872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42fc3e9adba8251795dbd8cceec1db225f2ed436","datavalue":{"value":{"entity-type":"item","numeric-id":393900,"id":"Q393900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"513bc9a0589f0d8e115b77059cac40bfad755864","datavalue":{"value":{"amount":"+0.6663987636566162","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":"Q2633234$E49294C3-60D5-4FBD-8F4D-9D15420937E8","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":"Q2633234$61A93A87-5EEE-4719-B144-F4744725A6F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analytic combinatorics for computing seeding probabilities","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analytic_combinatorics_for_computing_seeding_probabilities"}}}}}