<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">QP will be talking about Jellyfish tomorrow at 12p.<div><br></div><div><div><span class="Apple-style-span" style="font-family: 'Lucida Grande', 'Lucida Sans Unicode', Tahoma, Verdana, Arial, Helvetica, sans-serif; font-size: 11px; line-height: 14px; "><h1 id="article-title-1" style="margin-top: 10px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: bold; font-style: inherit; font-size: 1.8em; font-family: Georgia, 'Times New Roman', serif; line-height: inherit; text-align: left; vertical-align: baseline; border-style: initial; border-color: initial; ">A fast, lock-free approach for efficient parallel counting of occurrences of <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mers</h1><div><br></div><div><ol class="contributor-list" id="contrib-group-1" style="margin-top: 15px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: bold; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: left; vertical-align: baseline; list-style-type: none; list-style-position: initial; list-style-image: initial; white-space: normal; "><li class="contributor" id="contrib-1" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: inherit; font-family: inherit; line-height: 1.7; text-align: left; vertical-align: baseline; border-style: initial; border-color: initial; display: inline; white-space: normal; "><span class="name" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; "><a class="name-search" href="http://bioinformatics.oxfordjournals.org/search?author1=Guillaume+Mar%C3%A7ais&sortspec=date&submit=Submit" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: bold; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: 0px; color: rgb(0, 0, 204); text-decoration: none; white-space: nowrap; ">Guillaume Marçais</a></span><a id="xref-aff-1-1" class="xref-aff" href="http://bioinformatics.oxfordjournals.org/content/early/2011/01/07/bioinformatics.btr011.abstract#aff-1" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: normal; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: 0.2em; color: rgb(0, 0, 204); text-decoration: none; "><sup style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: 0.85em; font-family: inherit; line-height: 0; text-align: inherit; vertical-align: super; ">1</sup></a><span class="xref-sep" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: 0.33em; ">,</span><a id="xref-corresp-1-1" class="xref-corresp" href="http://bioinformatics.oxfordjournals.org/content/early/2011/01/07/bioinformatics.btr011.abstract#corresp-1" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: normal; font-style: inherit; font-size: 0.85em; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: super; color: rgb(0, 0, 204); text-decoration: none; ">*</a> and </li><li class="last" id="contrib-2" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: inherit; font-family: inherit; line-height: 1.7; text-align: left; vertical-align: baseline; border-style: initial; border-color: initial; display: inline; white-space: normal; "><span class="name" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; "><a class="name-search" href="http://bioinformatics.oxfordjournals.org/search?author1=Carl+Kingsford&sortspec=date&submit=Submit" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: bold; font-style: inherit; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: 0px; color: rgb(0, 0, 204); text-decoration: none; white-space: nowrap; ">Carl Kingsford</a></span></li></ol></div><div><br></div><div><span class="Apple-style-span" style="line-height: 16px; "> Counting the number of occurrences of every <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mer (substring of length <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>) in a long string is a central subproblem in many applications, including genome assembly, error correction of sequencing reads, fast multiple sequence alignment, and repeat detection. Recently, the deep sequence coverage generated by next-generation sequencing technologies has caused the amount of sequence to be processed during a genome project to grow rapidly, and has rendered current <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mer counting tools too slow and memory intensive. At the same time, large multi-core computers have become commonplace in research facilities allowing for a new parallel computational paradigm.</span></div><div><span class="Apple-style-span" style="line-height: 16px; "><br></span></div><div><span class="Apple-style-span" style="line-height: 16px; ">We propose a new <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mer counting algorithm and associated implementation, called Jellyfish, which is fast and memory efficient. It is based on a multi-threaded, lock-free hash table optimized for counting <em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mers up to 31 bases in length. Due to their flexibility, suffix arrays have been the data structure of choice for solving many string problems. For the task of<em style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-style: initial; border-color: initial; outline-style: none; font-weight: inherit; font-style: italic; font-size: inherit; font-family: inherit; line-height: inherit; text-align: inherit; vertical-align: baseline; ">k</em>-mer counting, important in many biological applications, Jellyfish offers a much faster and more memory efficient solution.</span></div></span><div><br></div></div><div><a href="http://bioinformatics.oxfordjournals.org/content/early/2011/01/07/bioinformatics.btr011.abstract">http://bioinformatics.oxfordjournals.org/content/early/2011/01/07/bioinformatics.btr011.abstract</a></div><div><br></div><div>See you. </div></div></body></html>