+ \item Spaced seed matches once
+ \item Consecutive seed never matches
+ \item Consecutive seed does more comparisons and may match
+ repeatedly
+ \end{itemize}
+\end{columns}
+\end{frame}
+
+\begin{frame}{Optimal Spaced Seed}
+ \begin{itemize}
+ \item Fewest overlaps with shifted seed
+ \item Longer seeds are better
+ \item Equivalent weight
+ \item Use dynamic programming to calculate optimal seed for given
+ length
+ \end{itemize}
+ \begin{columns}
+ \column{0.6\textwidth}
+ \begin{block}{DIAMOND Seeds (Fast)}
+ \begin{itemize}
+ \item 111101011101111 (12)
+ \item 111011001100101111 (12)
+ \item 1111001001010001001111 (12)
+ \item 111100101000010010010111 (12)
+ \end{itemize}
+ \end{block}
+\end{columns}
+\end{frame}
+
+\begin{frame}{Double Indexing}
+ \begin{itemize}
+ \item Blastx indexes the database
+ \item Blastx runs the queries in input order
+ \item DIAMOND indexes both the database and the queries
+ \item DIAMOND runs queries in index order
+ \item Why is this faster?
+ \end{itemize}
+\end{frame}
+
+\begin{frame}{Double Indexing: Why it's faster}
+ \begin{itemize}
+ \item Cache architecture
+ \begin{itemize}
+ \item On CPU Cache -- L1,L2
+ \item Shared CPU Cache L3
+ \item Much faster than main memory
+ \end{itemize}
+ \item Each cache miss must hit main memory (must hit northbridge,
+ which has significantly more latency than main cache, and takes
+ hundreds of cycles)
+ \item Dictionary Example: Is it faster to look up
+ \begin{itemize}
+ \item “apple”, “xylophone”, “appliance”, “xylem”
+ \item or “apple”, “appliance”, “xylem”, “xylophone”?
+ \end{itemize}
+ \end{itemize}