\documentclass{article}
\usepackage{amsmath,amsfonts,amsthm}
\title{2014 Symposium for Young Combinatorialists}
\author{Junyi Guo \\
Department of Applied Mathematics\\
National Chiaotung University\\
E-mail: junyiguo@gmail.com}
\date{}
\begin{document}
\maketitle
\begin{center}
Advisor: David Guo
\end{center}
There are two general approaches to the longest common subsequence
problem. The dynamic programming approach takes quadratic time but
linear space, while the non-dynamic-programming approach takes
less time but more space. We propose a new implementation of the
latter approach which seems to get the best for both time and
space for the DNA application.
Mutations in DNA arise naturally in an evolution process. These
mutations include substitutions, insertions and deletions of
nucleotides, leading to ``editing" of DNA texts. A sequence
comparison of two DNA sequences attempts to align the two
sequences to minimize a function of these mutations. The most
commonly used function is the so-called edit distance first
introduced by Levenshtein which simply counts the
number of mutations. If substitutions are not allowed, then the
alignment minimizing the edit distance will produce a longest
common subsequence (LCS) of the two sequences. Note that the LCS
problem had been studied by mathematicians for general sequences
long before the edit distance was introduced for DNA sequences.
\textbf{Keywords}: LCS, Longest Common Subsequence,
dynamic programming, DNA sequencing.
\end{document}