{"data":{"id":"10.6084/m9.figshare.791582","type":"dois","attributes":{"doi":"10.6084/m9.figshare.791582","prefix":"10.6084","suffix":"m9.figshare.791582","identifiers":[],"alternateIdentifiers":[],"creators":[{"name":"Rajat Roy","affiliation":[],"nameIdentifiers":[]},{"name":"Debashish Bhattacharya","affiliation":[],"nameIdentifiers":[]},{"name":"Schleip, Alexander","nameType":"Personal","givenName":"Alexander","familyName":"Schleip","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Turtle"}],"publisher":"figshare","container":{},"publicationYear":2013,"subjects":[{"subject":"Computational Biology"},{"subject":"60102 Bioinformatics","subjectScheme":"FOR"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"Applied Computer Science"}],"contributors":[],"dates":[{"date":"2013-09-07","dateType":"Created"},{"date":"2015-12-02","dateType":"Updated"},{"date":"2013","dateType":"Issued"}],"language":null,"types":{"ris":"DATA","bibtex":"misc","citeproc":"dataset","schemaOrg":"Dataset","resourceType":"Dataset","resourceTypeGeneral":"Dataset"},"relatedIdentifiers":[],"relatedItems":[],"sizes":["83914446 Bytes"],"formats":[],"version":null,"rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"We present a novel method that balances time, space and accuracy requirements to efficiently extract frequent k-mers even for high coverage libraries and large genomes such as human. Our method is designed to minimize cache-misses in a cache-efficient manner by using a Pattern-blocked Bloom filter to remove infrequent k-mers from consideration in combination with a novel sort-and-compact scheme, instead of a Hash, for the actual counting. While this increases theoretical complexity, the savings in cache misses reduce the empirical running times. A variant can resort to a counting Bloom filter for even larger savings in memory at the expense of false negatives in addition to the false positives common to all Bloom filter based approaches. A comparison to the state-of-the-art shows reduced memory requirements and running times.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjEvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC42MDg0L005LkZJR1NIQVJFLjc5MTU4MjwvaWRlbnRpZmllcj4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lPlJhamF0IFJveTwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lPkRlYmFzaGlzaCBCaGF0dGFjaGFyeWE8L2NyZWF0b3JOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZT5BbGV4YW5kZXIgU2NobGVpcDwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPlR1cnRsZTwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij4mbHQ7cCZndDtXZSBwcmVzZW50IGEgbm92ZWwgbWV0aG9kIHRoYXQgYmFsYW5jZXMgdGltZSwgc3BhY2UgYW5kIGFjY3VyYWN5IHJlcXVpcmVtZW50cyB0byBlZmZpY2llbnRseSBleHRyYWN0IGZyZXF1ZW50IGstbWVycyBldmVuIGZvciBoaWdoIGNvdmVyYWdlIGxpYnJhcmllcyBhbmQgbGFyZ2UgZ2Vub21lcyBzdWNoIGFzIGh1bWFuLiBPdXIgbWV0aG9kIGlzIGRlc2lnbmVkIHRvIG1pbmltaXplIGNhY2hlLW1pc3NlcyBpbiBhIGNhY2hlLWVmZmljaWVudCBtYW5uZXIgYnkgdXNpbmcgYSBQYXR0ZXJuLWJsb2NrZWQgQmxvb20gZmlsdGVyIHRvIHJlbW92ZSBpbmZyZXF1ZW50IGstbWVycyBmcm9tIGNvbnNpZGVyYXRpb24gaW4gY29tYmluYXRpb24gd2l0aCBhIG5vdmVsIHNvcnQtYW5kLWNvbXBhY3Qgc2NoZW1lLCBpbnN0ZWFkIG9mIGEgSGFzaCwgZm9yIHRoZSBhY3R1YWwgY291bnRpbmcuIFdoaWxlIHRoaXMgaW5jcmVhc2VzIHRoZW9yZXRpY2FsIGNvbXBsZXhpdHksIHRoZSBzYXZpbmdzIGluIGNhY2hlIG1pc3NlcyByZWR1Y2UgdGhlIGVtcGlyaWNhbCBydW5uaW5nIHRpbWVzLiBBIHZhcmlhbnQgY2FuIHJlc29ydCB0byBhIGNvdW50aW5nIEJsb29tIGZpbHRlciBmb3IgZXZlbiBsYXJnZXIgc2F2aW5ncyBpbiBtZW1vcnkgYXQgdGhlIGV4cGVuc2Ugb2YgZmFsc2UgbmVnYXRpdmVzIGluIGFkZGl0aW9uIHRvIHRoZSBmYWxzZSBwb3NpdGl2ZXMgY29tbW9uIHRvIGFsbCBCbG9vbSBmaWx0ZXIgYmFzZWQgYXBwcm9hY2hlcy4gQSBjb21wYXJpc29uIHRvIHRoZSBzdGF0ZS1vZi10aGUtYXJ0IHNob3dzIHJlZHVjZWQgbWVtb3J5IHJlcXVpcmVtZW50cyBhbmQgcnVubmluZyB0aW1lcy4mbHQ7L3AmZ3Q7PC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdD5Db21wdXRhdGlvbmFsICBCaW9sb2d5PC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc2NoZW1lVVJJPSJodHRwOi8vd3d3LmFicy5nb3YuYXUvYXVzc3RhdHMvYWJzQC5uc2YvMC82QkI0MjdBQjk2OTZDMjI1Q0EyNTc0MTgwMDA0NDYzRSIgc3ViamVjdFNjaGVtZT0iRk9SIj42MDEwMiBCaW9pbmZvcm1hdGljczwvc3ViamVjdD4KICAgIDxzdWJqZWN0PkFwcGxpZWQgQ29tcHV0ZXIgU2NpZW5jZTwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxwdWJsaXNoZXI+Zmlnc2hhcmU8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTM8L3B1YmxpY2F0aW9uWWVhcj4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQ3JlYXRlZCI+MjAxMy0wOS0wNzwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIj4yMDE1LTEyLTAyPC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJEYXRhc2V0Ij5EYXRhc2V0PC9yZXNvdXJjZVR5cGU+CiAgPHNpemVzPgogICAgPHNpemU+ODM5MTQ0NDYgQnl0ZXM8L3NpemU+CiAgPC9zaXplcz4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwczovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnkvNC4wLyI+Q0MgQlkgNC4wPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0Pgo8L3Jlc291cmNlPg==","url":"https://figshare.com/articles/dataset/Turtle/791582","contentUrl":null,"metadataVersion":2,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2013-09-07T16:02:29.000Z","registered":"2013-09-07T16:02:30.000Z","published":"2013","updated":"2020-09-05T01:29:07.000Z"},"relationships":{"client":{"data":{"id":"figshare.ars","type":"clients"}},"provider":{"data":{"id":"otjm","type":"providers"}},"media":{"data":{"id":"10.6084/m9.figshare.791582","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}