\relax 
\citation{pmid16056220}
\citation{pmid18660515}
\citation{pmid21576222}
\citation{pmid19023044}
\citation{pmid18809713}
\citation{pmid23953119}
\citation{pmid5420325}
\citation{ukkonen}
\newlabel{^_1}{{}{1}}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Methods}{1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.1}}Inexact string matching using tries}{1}}
\citation{WuManber1992}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Needleman-Wunsch (NW) sequence comparison. \textbf  {a} Comparison of GTTGCA and GATCCA. The margins of the edit matrix (purple) are initialized and the cells (yellow) are computed from left to right and from top to bottom by the NW dynamic programming algorithm. $E[i,j]$, the term of coordinates $(i,j)$ is computed as $\qopname  \relax m{min}(E[i-1,j]+1, E[i,j-1]+1, E[i-1,j-1]+\Delta (i,j))$, where $\Delta (i,j) = 0$ if the $i$-th symbol from the first sequence is the same as the $j$-th symbol from the second, and $\Delta (i,j) = 1$ otherwise. The Levenshtein distance between the two sequences is the value of the bottom right cell. \textbf  {b} Lower complexity algorithm to determine whether GTTGCA and GATCCA are 2-matches. The values in the purple cells are set during initialization. The dynamic programming algorithm proceeds as above, with the difference that it is aborted if the value of a diagonal cell (bold borders) is larger than 2. The values in the purple cells may differ from the original NW scheme (purple arrow), but the values in the yellow cells are nevertheless identical. The values of the white cells are never computed, which contributes to reducing the complexity.}}{2}}
\newlabel{fig:NW}{{1}{2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.2}}The poucet search algorithm}{2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.3}}Lossless filtration}{2}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces NW algorithm on tries. Each sequence of the index is a path in the trie. The query GTTGCA is written at the top of the matrix, which is initialized as shown on Figure 1\hbox {}b. The trie is traversed by a depth-first search (red path). At each depth, the node added to the path is written on the left of the edit matrix and the row is computed. Checkpoints from 1 to 4 (circled red numbers) show the state of the edit matrix as the search proceeds. The node labeled 3 is a leaf and thus corresponds to a 2-match of the query. After discovering the hit, the search path backtracks to the node labeled 2 and the last rows of the edit matrix are erased. The search path then goes to the node labeled 4, in which case the newly computed diagonal cell exceeds the threshold (circled in red). Even if this node has children, they are not visited (red crosses) because there is no 2-match to discover.}}{2}}
\newlabel{fig:trie}{{2}{2}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Poucet search algorithm. The algorithm proceeds with the same principles as shown on Figure 2\hbox {} with the difference that the edit matrix is not updated row-wise, but along a horizontally flipped L. As the depth-first search proceeds, these values are stored in the nodes of the trie. Since the values in the vertical part of the flipped L are the same for every child of a node, they are computed only once (purple arrow). The values in the grey cells will be computed as the search path (red) visits the node. Storing the intermediates in the nodes allows the next query to restart at depth $k$ if it shares a common prefix of length $k$ with the current query.}}{2}}
\newlabel{fig:poucet}{{3}{2}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Lossless filtration illustrated by an example sequence of length 20 with $\tau =3$. The last $\tau $ nucleotides of the query are removed, and the rest is divided into 4 series of contiguous segments. Each series is queried against a different index numbered I to IV. For instance, the only segment queried against index I is GTTG, while those queried against index II are GCAA, CAAT and AATA. If any of the segments is found in the appropriate index, the trie search is performed, otherwise it is omited as there can be no $\tau $-match. Regardless of the result, segments labelled I to IV are then added to the corresponding respective index (\textit  {i.e.} only one segment is added to each index).}}{3}}
\newlabel{fig:filtration}{{4}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.4}}Seek and construct}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.5}}Parallelization}{3}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Starcode algorithm}}{3}}
\newlabel{alg:starcode}{{1}{3}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Poucet search algorithm}}{3}}
\newlabel{alg:poucet}{{2}{3}}
\citation{mackay}
\citation{pmid21148542}
\citation{pmid21810899}
\citation{pmid22942077}
\citation{pmid23060610}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.6}}Clustering}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{2.7}}Benchmark conditions}{4}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Software execution options used in simulation benchmark.}}{4}}
\newlabel{tab:params1}{{1}{4}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Software execution options used in real data benchmark.}}{4}}
\newlabel{tab:params2}{{2}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Results}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{3.1}}Presentation and basic performance}{4}}
\newlabel{section:performance}{{{3.1}}{4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{3.2}}Benchmark}{4}}
\newlabel{section:benchmark}{{{3.2}}{4}}
\citation{pmid23953119}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Scalability. \textbf  {a} Logarithm of the running time versus the logarithm of the number of sequences to be clustered. \textbf  {b} Running time as a function of the clustering distance. \textbf  {c} Running time versus length of the input sequences. \textbf  {d} Relative performance increase for different number of parallel threads. }}{5}}
\newlabel{fig:perf}{{5}{5}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Benchmark results on artificial datasets of known cluster structure (see main text). \textbf  {a} Accuracy measured by the number of identified clusters. Starcode identifies the correct number of clusters, while seed and cd-hit identify about 40 false positives per true positive. The red line is the first bisector and indicates perfect results. \textbf  {b} Accuracy measured by the number of identified pairs. Slidesort identifies 5-10\% less pairs than starcode. The red line indicates a ratio of 1. \textbf  {c} Running time of the different tools. As the size of the clusters the running time of starcode increases but remains competitive. \textbf  {d} Memory usage of the different tools. The memory usage of starcode decreases as the size of the cluster increases.}}{5}}
\newlabel{fig:benchmark}{{6}{5}}
\citation{pmid10673000}
\citation{pmid19561594}
\citation{pmid23562324}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces Summary of the biological datasets used for benchmarking. All the datasets are Illumina reads.}}{6}}
\newlabel{tab:biobench_properties}{{3}{6}}
\@writefile{lot}{\contentsline {table}{\numberline {4}{\ignorespaces Running time (in seconds) of the software on three biological datasets. Exact running time was not recordeed past 10 days. A dash indicates that the software cannot be used for this dataset.}}{6}}
\newlabel{tab:biobench_runtime}{{4}{6}}
\@writefile{lot}{\contentsline {table}{\numberline {5}{\ignorespaces Memory usage (in GB).}}{6}}
\newlabel{tab:biobench_memory}{{5}{6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {{3.3}}Identifying enriched sequence motifs}{6}}
\newlabel{section:motifs}{{{3.3}}{6}}
\citation{pmid23253355}
\bibstyle{natbib}
\bibdata{document}
\bibcite{pmid23953119}{{1}{2013}{{Akhtar {\em  et~al.}}}{{Akhtar, de~Jong, Pindyurin, Pagie, Meuleman, de~Ridder, Berns, Wessels, van Lohuizen, and van Steensel}}}
\bibcite{pmid21810899}{{2}{2011}{{Bao {\em  et~al.}}}{{Bao, Jiang, Kaloshian, and Girke}}}
\bibcite{pmid22942077}{{3}{2012}{{Chong {\em  et~al.}}}{{Chong, Ruan, and Wu}}}
\bibcite{pmid23253355}{{4}{2013}{{Daubner {\em  et~al.}}}{{Daubner, Cléry, and Allain}}}
\bibcite{pmid18660515}{{5}{2008}{{Dohm {\em  et~al.}}}{{Dohm, Lottaz, Borodina, and Himmelbauer}}}
\bibcite{pmid19023044}{{6}{2009}{{Eid {\em  et~al.}}}{{Eid, Fehr, Gray, Luong, Lyle, Otto, Peluso, Rank, Baybayan, Bettman, Bibillo, Bjornson, Chaudhuri, Christians, Cicero, Clark, Dalal, Dewinter, Dixon, Foquet, Gaertner, Hardenbol, Heiner, Hester, Holden, Kearns, Kong, Kuse, Lacroix, Lin, Lundquist, Ma, Marks, Maxham, Murphy, Park, Pham, Phillips, Roy, Sebra, Shen, Sorenson, Tomaney, Travers, Trulson, Vieceli, Wegener, Wu, Yang, Zaccarin, Zhao, Zhong, Korlach, and Turner}}}
\bibcite{pmid23060610}{{7}{2012}{{Fu {\em  et~al.}}}{{Fu, Niu, Zhu, Wu, and Li}}}
\bibcite{mackay}{{8}{2002}{{MacKay}}{{MacKay}}}
\bibcite{pmid16056220}{{9}{2005}{{Margulies {\em  et~al.}}}{{Margulies, Egholm, Altman, Attiya, Bader, Bemben, Berka, Braverman, Chen, Chen, Dewell, Du, Fierro, Gomes, Godwin, He, Helgesen, Ho, Ho, Irzyk, Jando, Alenquer, Jarvie, Jirage, Kim, Knight, Lanza, Leamon, Lefkowitz, Lei, Li, Lohman, Lu, Makhijani, McDade, McKenna, Myers, Nickerson, Nobile, Plant, Puc, Ronan, Roth, Sarkis, Simons, Simpson, Srinivasan, Tartaro, Tomasz, Vogt, Volkmer, Wang, Wang, Weiner, Yu, Begley, and Rothberg}}}
\bibcite{pmid21576222}{{10}{2011}{{Nakamura {\em  et~al.}}}{{Nakamura, Oshima, Morimoto, Ikeda, Yoshikawa, Shiwa, Ishikawa, Linak, Hirai, Takahashi, Altaf-Ul-Amin, Ogasawara, and Kanaya}}}
\bibcite{pmid5420325}{{11}{1970}{{Needleman and Wunsch}}{{Needleman and Wunsch}}}
\bibcite{pmid23562324}{{12}{2013}{{Pandit {\em  et~al.}}}{{Pandit, Zhou, Shiue, Coutinho-Mansfield, Li, Qiu, Huang, Yeo, Ares, and Fu}}}
\bibcite{pmid19561594}{{13}{2009}{{Ray {\em  et~al.}}}{{Ray, Kazan, Chan, Castillo, Chaudhry, Talukder, Blencowe, Morris, and Hughes}}}
\bibcite{pmid18809713}{{14}{2008}{{Schepers {\em  et~al.}}}{{Schepers, Swart, van Heijst, Gerlach, Castrucci, Sie, Heimerikx, Velds, Kerkhoven, Arens, and Schumacher}}}
\bibcite{pmid21148542}{{15}{2011}{{Shimizu and Tsuda}}{{Shimizu and Tsuda}}}
\bibcite{pmid10673000}{{16}{1999}{{Smith {\em  et~al.}}}{{Smith, Gwinn, and Salzberg}}}
\bibcite{ukkonen}{{17}{1995}{{Ukkonen}}{{Ukkonen}}}
\bibcite{WuManber1992}{{18}{1992}{{Wu and Manber}}{{Wu and Manber}}}
\global\@namedef{@lastpage@}{7}
\@writefile{toc}{\contentsline {section}{\numberline {4}Discussion and conclusion}{7}}
\@writefile{toc}{\contentsline {paragraph}{Funding\text  {\rm  :}}{7}}
