{"data":{"id":"10.6084/m9.figshare.791579","type":"dois","attributes":{"doi":"10.6084/m9.figshare.791579","prefix":"10.6084","suffix":"m9.figshare.791579","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 Software."}],"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":["148461 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\u003cbr\u003econsideration 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\u003cbr\u003ethe 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\u003cbr\u003eall Bloom filter based approaches. A comparison to the state-of-the-art shows reduced memory requirements and running times.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjEvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC42MDg0L005LkZJR1NIQVJFLjc5MTU3OTwvaWRlbnRpZmllcj4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lPlJhamF0IFJveTwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lPkRlYmFzaGlzaCBCaGF0dGFjaGFyeWE8L2NyZWF0b3JOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZT5BbGV4YW5kZXIgU2NobGVpcDwvY3JlYXRvck5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPlR1cnRsZSBTb2Z0d2FyZS48L3RpdGxlPgogIDwvdGl0bGVzPgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+Jmx0O3AmZ3Q7V2UgcHJlc2VudCBhIG5vdmVsIG1ldGhvZCB0aGF0IGJhbGFuY2VzIHRpbWUsIHNwYWNlIGFuZCBhY2N1cmFjecKgcmVxdWlyZW1lbnRzIHRvIGVmZmljaWVudGx5IGV4dHJhY3QgZnJlcXVlbnQgay1tZXJzIGV2ZW4gZm9yIGhpZ2jCoGNvdmVyYWdlIGxpYnJhcmllcyBhbmQgbGFyZ2UgZ2Vub21lcyBzdWNoIGFzIGh1bWFuLiBPdXIgbWV0aG9kIGlzwqBkZXNpZ25lZCB0byBtaW5pbWl6ZSBjYWNoZS1taXNzZXMgaW4gYSBjYWNoZS1lZmZpY2llbnQgbWFubmVyIGJ5IHVzaW5nwqBhIFBhdHRlcm4tYmxvY2tlZCBCbG9vbSBmaWx0ZXIgdG8gcmVtb3ZlIGluZnJlcXVlbnQgJGskLW1lcnMgZnJvbSZsdDticiZndDtjb25zaWRlcmF0aW9uIGluIGNvbWJpbmF0aW9uIHdpdGggYSBub3ZlbCBzb3J0LWFuZC1jb21wYWN0wqBzY2hlbWUsIGluc3RlYWQgb2YgYSBIYXNoLCBmb3IgdGhlIGFjdHVhbCBjb3VudGluZy4gV2hpbGUgdGhpc8KgaW5jcmVhc2VzIHRoZW9yZXRpY2FsIGNvbXBsZXhpdHksIHRoZSBzYXZpbmdzIGluIGNhY2hlIG1pc3NlcyByZWR1Y2UmbHQ7YnImZ3Q7dGhlIGVtcGlyaWNhbCBydW5uaW5nIHRpbWVzLiBBIHZhcmlhbnQgY2FuIHJlc29ydCB0byBhIGNvdW50aW5nIEJsb29twqBmaWx0ZXIgZm9yIGV2ZW4gbGFyZ2VyIHNhdmluZ3MgaW4gbWVtb3J5IGF0IHRoZSBleHBlbnNlIG9mIGZhbHNlwqBuZWdhdGl2ZXMgaW4gYWRkaXRpb24gdG8gdGhlIGZhbHNlIHBvc2l0aXZlcyBjb21tb24gdG8mbHQ7YnImZ3Q7YWxsIEJsb29tIGZpbHRlciBiYXNlZCBhcHByb2FjaGVzLiBBIGNvbXBhcmlzb24gdG8gdGhlwqBzdGF0ZS1vZi10aGUtYXJ0IHNob3dzIHJlZHVjZWQgbWVtb3J5IHJlcXVpcmVtZW50cyBhbmQgcnVubmluZyB0aW1lcy4mbHQ7L3AmZ3Q7CiZsdDtwJmd0O8KgJmx0Oy9wJmd0OzwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3Q+Q29tcHV0YXRpb25hbCAgQmlvbG9neTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHNjaGVtZVVSST0iaHR0cDovL3d3dy5hYnMuZ292LmF1L2F1c3N0YXRzL2Fic0AubnNmLzAvNkJCNDI3QUI5Njk2QzIyNUNBMjU3NDE4MDAwNDQ2M0UiIHN1YmplY3RTY2hlbWU9IkZPUiI+NjAxMDIgQmlvaW5mb3JtYXRpY3M8L3N1YmplY3Q+CiAgICA8c3ViamVjdD5BcHBsaWVkIENvbXB1dGVyIFNjaWVuY2U8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8cHVibGlzaGVyPmZpZ3NoYXJlPC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDEzPC9wdWJsaWNhdGlvblllYXI+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IkNyZWF0ZWQiPjIwMTMtMDktMDc8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCI+MjAxNS0xMi0wMjwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iRGF0YXNldCI+RGF0YXNldDwvcmVzb3VyY2VUeXBlPgogIDxzaXplcz4KICAgIDxzaXplPjE0ODQ2MSBCeXRlczwvc2l6ZT4KICA8L3NpemVzPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHBzOi8vY3JlYXRpdmVjb21tb25zLm9yZy9saWNlbnNlcy9ieS80LjAvIj5DQyBCWSA0LjA8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CjwvcmVzb3VyY2U+","url":"https://figshare.com/articles/dataset/Turtle_Identifying_frequent_k_mers_with_cache_efficient_algorithms/791579","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-07T15:33:27.000Z","registered":"2013-09-07T15:33:28.000Z","published":"2013","updated":"2020-09-05T01:29:09.000Z"},"relationships":{"client":{"data":{"id":"figshare.ars","type":"clients"}},"provider":{"data":{"id":"otjm","type":"providers"}},"media":{"data":{"id":"10.6084/m9.figshare.791579","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}