A Brief Survey on Sequence Classification

Zhengzheng Xing Jian Pei Eamonn Keogh

School of Computing Science School of Computing Science Department and Computer
Simon Fraser University Simon Fraser University Science and Engineering
Burnaby, BC, Canada Burnaby, BC, Canada University of California,
Riverside, CA, USA
zxing@[Link] jpei@[Link]
eamonn@[Link]

ABSTRACT • A complex symbolic sequence is an ordered list of vec-

tors. Each vector is a subset of the alphabet [34]. For
Sequence classification has a broad range of applications
example, for a sequence of items bought by a cus-
such as genomic analysis, information retrieval, health in-
tomer over one year, treating each transaction as a
formatics, finance, and abnormal detection. Different from
vector, a sequence can be h(milk, bread)(milk, egg) · · ·
the classification task on feature vectors, sequences do not
(potatos, cheese, coke)i.
have explicit features. Even with sophisticated feature se-
lection techniques, the dimensionality of potential features • A simple time series is a sequence of real values or-
may still be very high and the sequential nature of features dered in timestamp ascending order. For example,
is difficult to capture. This makes sequence classification
a more challenging task than classification on feature vec- h(t1 , 0.1)(t2 , 0.3) · · · (tn , 0.3)i
tors. In this paper, we present a brief review of the existing is a simple time series recording the data from time
work on sequence classification. We summarize the sequence stamp t1 to tn .
classification in terms of methodologies and application do-
mains. We also provide a review on several extensions of the • A multivariate time series is a sequence of numerical
sequence classification problem, such as early classification vectors. For example,
on sequences and semi-supervised learning on sequences. h(t1 , h0.1, 0.3, 05i)(t2 , h0.3, 0.9, 0.8i)···(tn , h0.3, 0.9, 0.4i)i
is a multivariate time series.
1. INTRODUCTION
Sequence classification has a broad range of real-world appli- • In the above, the data types of the events are simple.
cations. In genomic research, classifying protein sequences In some applications, the data type of events can be ar-
into existing categories is used to learn the functions of a new bitrarily complicated. For example, in a patient record
protein [13]. In health-informatics, classifying ECG time se- data set ([Link]
ries (the time series of heart rates) tells if the data comes each patient is represented by a longitudinal sequence
from a healthy person or comes from a patient with heart of hospital visits. Each visit is an event and is de-
disease [59]. In anomaly detection/intrusion detection, the scribed by multiple numerical measurements, categor-
sequence of a user’s system access activities on Unix is mon- ical fields and text descriptions. A complex event se-
itored to detect abnormal behaviors [33]. In information re- quence refers to the general form of sequences.
trieval, classifying documents into different topic categories
has attracted a lot of attentions [51]. Other interesting ex- A sequence may carry a class label. For example, a time
amples include classifying query log sequences to distinguish series of ECG data may come from a healthy or ill person.
web-robots from human users [58; 18] and classifying trans- A DNA sequence may belong to a gene coding area or a
action sequence data in a bank for the purpose of combating non-coding area. Given L as a set class labels, the task of
money laundering [42]. (conventional) sequence classification is to learn a sequence
Generally, a sequence is an ordered list of events. An event classifier C, which is a function mapping a sequence s to a
can be represented as a symbolic value, a numerical real class label l ∈ L, written as, C : s → l, l ∈ L.
value, a vector of real values or a complex data type. In this In (conventional) sequence classification, each sequence is
paper, we consider sequence data into the following sub- associated with only one class label and the whole sequence
types. is available to a classifier before the classification. There are
also other application scenarios for sequence classification.
• Given an alphabet of symbols {E1 , E2 , E3 , ..., En }, a For example, for a sequence of symptoms of a patient over a
simple symbolic sequence is an ordered list of the sym- long period of time, the health condition of the patient may
bols from the alphabet. For example, a DNA sequence change. For a streaming sequence, which can be regarded
is composed of four animo acid A, C, G, T and a DNA as a virtually unlimited sequence, instead of predicting one
segment, such as ACCCCCGT , is a simple symbolic class label, it is more desirable to predict a sequence of la-
sequence. bels. This problem is considered in [24; 23] as the strong
sequence classification task. In this paper, we will discuss
several extensions of (conventional) sequence classification
in Section 3.

SIGKDD Explorations Volume 12, Issue 1

 There are three major challenges in sequence classification. a k-gram, is usually selected as a feature. Given a set of
First, most of the classifiers, such as decision trees and neu- k-grams, a sequence can be represented as a vector of the
ral networks, can only take input data as a vector of features. presence and the absence of the k-grams or as a vector of
However, there are no explicit features in sequence data. the frequencies of the k-grams. Sometimes, we also allow
Second, even with various feature selection methods, we can inexact matchings with gapped k-grams. By using k-grams
transform a sequence into a set of features, the feature se- as features, sequences can be classified by a conventional
lection is far from trivial. The dimensionality of the feature classification method, such as SVM [35; 36] and decision
space for the sequence data can be very high and the compu- trees [12]. A summary of k-gram based feature selection
tation can be costly. Third, besides accurate classification methods for sequence classifications can be found in [16].
results, in some applications, we may also want to get an The size of candidate features which are all k-grams where
interpretable classifier. Building an interpretable sequence 1 ≤ k ≤ l is 2l − 1. If k is a large number, the size of the
classifier is difficult since there are no explicit features. feature set can be huge. Since not all features are equally
In this paper, we give a brief survey of the existing sequence useful for classification, Chuzhanova et al. [12] use Gamma
classification methods. Since most of the existing works fo- test to select a small informative subset of features from
cus on the task of conventional sequence classification, Sec- the k-grams. A genetic algorithm is used to find the local
tion 2 is devoted to summarizing the major methods for optimal subset of features.
this task. In Section 3, we discuss some extensions of the In contrast to k-gram based feature selections, Lesh et al. [30;
conventional sequence classification tasks, such as streaming 34] propose a pattern-based feature selection method. The
sequence classification and early classification on sequences. features are short sequence segments which satisfy the fol-
In Section 4, we summarize sequence classification from the lowing criteria (1) frequent in at least one class (2) distinc-
perspective of application domains, such as time series data, tive in at least one class and (3) not redundant. Criterion
text data and genomic data. Section 5 concludes the paper. (2) means a feature should be significantly correlated with
at least one class. The redundancy in Criterion (3) can be
2. SEQUENCE CLASSIFICATION METH- defined in the way of feature specification and feature gener-
alization. An efficient feature mining algorithm is proposed
ODS to mine features according to the criteria. After selecting the
The sequence classification methods can be divided into features, Winnow [41] and naive bayes classifiers are used.
three large categories. The experimental results in [30] show that comparing to the
method of considering each element as a feature, pattern-
• The first category is feature based classification, which based feature selection can improve the accuracy by 10% to
transforms a sequence into a feature vector and then 15%.
apply conventional classification methods. Feature se- The challenge of applying pattern-based feature selection on
lection plays an important role in this kind of methods. symbolic sequences is how to efficiently search for the fea-
tures satisfying the criteria. Ji et al. [22] propose an algo-
• The second category is sequence distance based clas-
rithm to mine distinctive subsequences with a maximal gap
sification. The distance function which measures the
constraint. The algorithm, which uses bisect and boolean
similarity between sequences determines the quality of
operations and a prefix growth framework, is efficient even
the classification significantly.
with a low frequency threshold.
• The third category is model based classification, such Time series data is numeric. The feature selection tech-
as using hidden markov model (HMM) and other sta- niques for symbolic sequences cannot be easily applied to
tistical models to classify sequences. time series data without discretization. Discretization may
cause information lost. Ye et al. [65] propose a feature selec-
In the rest of this section, we will present some represen- tion method which can be applied directly on numeric time
tative methods in the three categories. Some methods may series. Time series shapelets, the time series subsequences
ride on multiple categories. For example, we can use SVM which can maximally represent a class, is proposed as the
by either extracting features (Category 1) or defining a dis- features for time series classification. For a two-class clas-
tance measure (Category 2). Sequence classification using sification task, given a distance threshold, a shapelet is a
SVM will be summarized in Section 2.3. All methods dis- segment of time series which can be used to separate the
cussed in this section are for conventional sequence classifi- training data into two parts according to the distance to
cation. the shapelet, and maximizes the information gain. The dis-
tance threshold and the shapelet are learned from the train-
2.1 Feature Based Classification ing data to optimize the information gain. To construct a
Conventional classification methods, such as decision trees classifier, the shapelet selection process is integrated with
and neural networks, are designed for classifying feature vec- the construction of the decision tree.
tors. One way to solve the problem of sequence classification Although subsequences are informative features, they can
is to transform a sequence into a vector of features through only describe the local properties of a long sequence. Ag-
feature selections. garwal et al. [5] develop a method to capture both the global
For a symbolic sequence, the simplest way is to treat each and local properties of sequences for the purpose of classifi-
element as a feature. For example, a sequence CACG can be cation. Aggarwal et al. [5] modify wavelet decomposition to
transformed as a vector hA, C, C, Gi. However, the sequen- describe a symbolic sequence on multiple resolutions. With
tial nature of sequences cannot be captured by this trans- different decomposition coefficients, the wavelet represents
formation. To keep the order of the elements in a sequence, the trends in different range of intervals, from global to lo-
a short sequence segment of k consecutive symbols, called cal. Using wavelet decomposition and a rule based classi-

SIGKDD Explorations Volume 12, Issue 1

 fier, the wavelet decomposition method outperforms the k-
nearest neighbor classifier on a web accessing sequence data
set and on a genomic sequence data set.
In summary, the existing methods differ from each other on
the following aspects.

• Which criteria should be used for selecting features,

such are distinctiveness, frequency, and length?

• In which scope does feature selection reflect the se- Figure 1: Dynamic Time Warping
quential nature of a sequence, local or global?

• Should matchings be exact or inexact with gaps? to prune may calculations. Xi et al. [61] use numerical re-
duction to speed up DTW computation. The idea is to
• Should feature selection be integrated within the pro- reduce the number of the training examples used by a 1NN
cess of constructing the classifier or a separate pre- classifier and, at the same time, adjust the warping window
processing step? dynamically.
For symbolic sequences, such as protein sequences and DNA
2.2 Sequence Distance Based Classification sequences, alignment based distances are popular adopted [25].
Sequence distance based methods define a distance func- Given a similarity matrix and a gap penalty, the Needleman-
tion to measure the similarity between a pair of sequences. Wunsch algorithm [44] computes an optimum global align-
Once such a distance function is obtained, we can use some ment score between two sequences through dynamic pro-
existing classification methods, such as K nearest neighbor gramming. In contrast to global alignment algorithms, lo-
classifier (KNN) and SVM with local alignment kernel (to cal alignment algorithms, such as the Smith-Waterman al-
be discussed in Section 2.3 [49], for sequence classification. gorithm [53] and BLAST [6], measure the similarity between
KNN is a lazy learning method and does not pre-compute two sequences by considering the most similar regions but
a classification model. Given a labeled sequence data set T , not enforcing the alignments on full length.
a positive integer k, and a new sequence s to be classified,
the KNN classifier finds the k nearest neighbors of s in T , 2.3 Support Vector Machine
kN N (s), and returns the dominating class label in kN N (s) SVM has been proved to be an effective method for sequence
as the label of s. classification [43; 39; 35; 54; 55; 52; 13]. The basic idea of
The choice of distance measures is critical to the perfor- applying SVM on sequence data is to map a sequence into a
mance of KNN classifiers. In the rest of this section, we feature space and find the maximum-margin hyperplane to
focus on summarizing different distance measures proposed separate two classes. Sometimes, we do not need to explic-
for sequence data. itly conduct feature selection. A kernel function corresponds
For simple time series classification, Euclidean distance is a to a high dimension feature space. Given two sequences,
widely adopted option [26; 59]. For two time series s and s0 , x, y, some kernel functions, K(x, y), can be viewed as the
Euclidean distance is similarity between two sequences [54]. The challenges of ap-
v plying SVM to sequence classification include how to define
u L
uX feature spaces or kernel functions, and how to speed up the
dist(s, s ) = t
0
(s[i] − s0 [i])2 . computation of kernel matrixes.
i=1
One of the widely used kernels for sequence classification
The Euclidean distance usually requires two time series to is k-spectrum kernel or string kernel, which transforms a
have the same length. Keogh et al. [26] show when applying sequence into a feature vector. Leslie et al. [35] propose a k-
1NN classifier on time series, Euclidean distance is surpris- spectrum kernel for protein classification. Given the protein
ingly competitive in terms of accuracy, compared to other animo acid alphabet of 20 elements hA, R, N, D · ··i, the k-
more complex similarity measures. spectrum is all the possible sequences of length k that are
Euclidean distance is sensitive to distortions in time dimen- composed by the elements in the alphabet. For example, if
sion. Dynamic time warping distance (DTW) [28] is pro- k = 3, the k-spectrum contains ARN, AND, DCN, and so
posed to overcome this problem and does not require two on. Given the alphabet A, a sequence x is transformed into
time series to be of the same length. The idea of DTW is a feature space by a transformation function
to align two time series and get the best distance by align- Φk (x) = (φa (x))a∈Ak
ing. One example of DTW is shown in Figure 1. Xi et
al. [61] show that on small data sets, elastic measures such where φa (x) is the number of times a occurs in x. The kernel
as dynamic time warping (DTW) can be more accurate than function is the dot product of the feature vectors,
Euclidean distance. However, recent empirical results [15] K(x, y) = Φk (x) · Φk (y)
strongly suggest that on large data sets, the accuracy of
elastic measures converges with Euclidean distance. By using a suffix tree algorithm [35], K(x, y) can be com-
Dynamic time warping is usually computed by dynamic pro- puted in O(kn) time.
gramming and has the quadratic time complexity. There- Lodhi et al. [43] propose a string kernel for text classifica-
fore, it is costly on a large data set. Ratanamahatana et tion. Similar to the k-spectrum kernel in [35], the string
al. [48] propose a method to dramatically speed up the kernel also uses a k-length sub-sequences but allows gaps.
DTW similarity search process by using tight lower bounds By using an exponentially decaying factor of the length of

SIGKDD Explorations Volume 12, Issue 1

 span of the subsequences occurring in the text, the gap is HMM to classify biological sequences. A profile HMM usu-
penalized. The kernel function is the dot product of the ally has three types of states, inserting, matching and delet-
feature vectors and can be efficiently computed by dynamic ing. Aligned training examples are used to learn the tran-
programming. Leslie et al. [36] extends the k-spectrum ker- sition probabilities between the states and emission prob-
nel to handle mismatching. Sonnenburg et al. [55] propose abilities. The learned HMM represents the profile of the
a fast k-spectrum kernel with mismatching . training dataset. A profile HMM may also be learned from
One disadvantage of kernel based methods is that it is hard the unaligned sequences by gradually aligning each example
to be interpreted and hard for users to gain knowledge be- with the existing profile. For each class, a profile HMM is
sides a classification result. Sonnenburg et al. propose a learned. In the classification step, an unknown sequence is
method to learn interpretable SVMs using a set of a string aligned with the profile HMM in each class by dynamic pro-
kernels [54]. The ideas is to use a weighted linear combi- gramming. An unknown sequence will be classified into the
nation of base kernels. Each base kernel uses a distinctive class which has the highest alignment score.
set of features. The weights represent the importance of the
features. After learning the SVM, users can have an insight
into the importance of different features.
3. EXTENSIONS OF SEQUENCE CLASSI-
String kernels or k-spectrum kernel can be viewed as a fea- FICATION
ture based method. Saigo et al. [49] propose a local align- In this section, we review some closely related or extended
ment kernel for protein sequence classification which can be problems of conventional sequence classification. Those ex-
viewed as a distance based method. Although local align- tensions are proposed to address the challenges when apply-
ment distance can effectively describe the similarity between ing sequence classification to different real world application
two sequences, it cannot be directly used as a kernel function scenarios, such as classifying a sequence using its prefixes to
because it lacks the positive definiteness property. Saigo et achieve early classification, classifying sequences by using
al. [49] modify the local alignment distance and form a valid both labeled and unlabeled data, and predicting a sequence
kernel called local alignment kernel, which mimics the be- of labels instead of a single label for streaming sequences.
havior of the local alignment. The theoretical connection
between the local alignment kernel and the local alignment 3.1 Early Classification
distance is proved. Given two sequences x, y, the local align- For temproal symbolic sequences and time series, the values
ment kernel K(x, y) can be computed by dynamic program- of a sequence are received in time stamp ascending order.
ming. Sometimes, monitoring and classifying sequences as early as
Other kernels used for sequence classification include polynomial- possible is desired. For example, in a retrospective study of
like kernels [52], kernels derived from probabilistic model the infants admitted to a neonatal intensive care unit, it is
(Fisher’s kernel) [52], and diffusion kernels [50]. found that the infants had abnormal heart beating time se-
ries pattern 24 hour before the doctor finally diagnosed them
2.4 Model Based Classification with sepsis [21]. As another example, Bernaille et al. [9]
One category of sequence classification methods is based on show that by only observing the first five packages of a TCP
generative models, which assume sequences in a class are connection, the application associated with the traffic flow
generated by an underlying model M . Given a class of se- can be classified. The applications of online traffic can be
quences, M models the probability distribution of the se- identified without waiting for the TCP flow to end. Gener-
quences in the class. Usually, a model is defined based on ally, early classification of sequences may have applications
some assumptions, and the probability distributions are de- in anomaly detection, intrusion detection, health informat-
scribed by a set of parameters. In the training step, the ics, and process control.
parameters of M are learned. In the classification step, a To the best of our knowledge, Diez et al. [14] first mentioned
new sequence is assigned to the class with the highest like- the concept of early classification of time series. They de-
lihood. scribe a time series by some relative literals, such as “in-
The simplest generative model is the Naive Bayes sequence crease” and “stay”, and some region literals, such as “al-
classifier [37]. It makes the assumption that, given a class, ways” and “sometimes” over some intervals. Each literal
the features in the sequences are independent of each other. and its associated position are viewed as a base classifier.
The conditional probabilities of the features in a class are Ada boost [19] is used to ensemble the base classifiers. The
learned in the training step. Due to its simplicity, Naive ensemble classifier is capable of making predictions on in-
Bayes has been widely used from text classification [29] and complete data by viewing unavailable suffixes of sequences
genomic sequences classification [11]. as missing features.
However, the independence assumption required by Naive Anibal et al. [8] apply a case based reasoning method to
Bayes is often violated in practice. Markov Model and Hid- classify time series to monitor the system failure in a simu-
den Markov Model can model the dependence among ele- lated dynamic system. The KNN classifier is used to clas-
ments in sequences [17]. sify incomplete time series using various distances, such as
Yakhnenko et al. [64] apply a k-order Markov model to clas- Euclidean distance and Dynamic time warping (DTW) dis-
sify protein and text sequence data. In the training process, tance. The simulation studies show that, by using case based
the model is trained in a discriminative setting instead of the reasoning, the most important increase of classification ac-
conventional generative setting to increase the classification curacy occurs on the prefixes through thirty to fifty percent
power of the generative model based methods. of the full length.
Different from Markov Model, Hidden Markov Model as- Although in [14; 8], the importance of early classification
sumes that the system being modeled is a Markov process on time series is identified and some encouraging results are
with unobserved states. Srivastava et al. [56] use a profile shown, the study only treat early classification as a problem

SIGKDD Explorations Volume 12, Issue 1

 of classifying prefixes of sequences. Xing et al. [62] point out only a small amount of labeled data in the positive class is
the challenge of early classification is to study the tradeoff available. In the training step, at the beginning, all the un-
between the earliness and the accuracy of classification. The labeled data is regarded as negative. Then, a 1NN classifier
methods proposed in [14; 8] only focus on making predic- is applied to classify unlabeled data in iteration until the the
tions based on partial information but do not address how stopping criteria is met. Wei et al. [59] propose a heuristic
to select the shortest prefix to provide a reliable prediction. stopping criteria. In the iteration of labeling more time se-
This makes the result of early classification cannot be easily ries as positive, they observe that the minimum distance in
used by users for further actions the positive class will first decrease and then experience a
Xing et al. [62] formulate the early classification problem as plateau, and at last decrease again. The iteration will stop
classifying sequences as early as possible while maintaining when the minimum distance in the positive class starting to
an expected accuracy. A feature based method is proposed decrease after the plateau.
for early classification on temporal symbolic sequences. The Weston et al. [60] propose a semi-supervised protein classi-
major idea is to first select a set of features that are fre- fication method by using SVM with a cluster kernel. The
quent, distinctive and early, and then build an association kernel function between two sequences is defined as the dis-
rule classifier or a decision tree classifier using those features. tance between two clusters of sequences. The two clusters
In the classification step, an oncoming sequence is matched are the neighborhoods of the two sequences, and the distance
with all rules or branches simultaneously until on a prefix, a of the two clusters is the average pair-wise inter-cluster dis-
matching is found and the sequence is classified. In this way, tance. The neighborhood of a sequence may contain labeled
a sequence is classified immediately once the user expected and unlabeled sequences. By using the cluster kernel, the
accuracy is achieved. The methods proposed in [62] show information of the unlabeled data can be utilized. The re-
some successes in handling symbolic sequences by achieving sults show that by adding unlabeled data, the cluster kernel
competitive accuracies using only less than half of the length works better than only using labeled data.
of the full sequences.
One disadvantage of the methods in [62] is that it cannot 3.3 Sequence Classification with A Sequence
handle numeric time series well. Since numeric time series of Labels
need to be discretized online, the information loss makes As discussed in Section 1, for streaming sequence classifica-
some distinctive features not easy to capture. Xing et al. [63] tion, instead of predicting one class label, it is more desirable
propose an early classifier for numeric time series by utiliz- to predict a sequence of labels. Kadous [24; 23] identifies this
ing instance based learning. The method learns a minimal problem as strong sequence classification task but does not
prediction length (MPL) for each time series in the training provide a solution for this problem.
dataset through clustering and uses MPLs to guide early A closely related problem considered in natural language
classification. As shown in Section 2, 1NN classifier with processing is called labeling sequences [31; 7; 20]. The task
Euclidean distance is a highly accurate classifier for time se- is to label each element in a sequence. For example, given
ries classification. One interesting property of the method a sentence, where each word is treated as an element, se-
in [63] is that without requiring a user expected accuracy, quence labeling is to assign each word to a category, such as
the classifier can achieve early classification while maintain name identity, noun phrase, verb phrase etc. The straight-
roughly the same accuracy as a 1NN classifier using full forward solution is to label each element independently. An
length time series. advanced solution is to consider the labels of the elements
in a sequence related to each other. Sequence labeling prob-
3.2 Semi-Supervised Sequence Classification lem has been solved by using conditional random fields [31].
There are usually more unlabeled data than labeled data. The problem has also been tackled by other methods, such
Some unlabeled data shares common features with labeled as using a combined model of HMM and SVM [7] and using
data and also contains extra features which may provide a a recurrent neural network [20].
more comprehensive description of a class. Therefore, by
incorporating unlabeled data, sometimes, a more accurate
classifier may be built.
4. APPLICATIONS OF SEQUENCE CLAS-
For text classification, there is a large amount of unlabeled SIFICATION
data. Nigam et al. [46] propose a semi-supervised classifi- Sequence classification has a broad range of applications.
cation method to label documents. Initially, a Naive Bayes For different application domains, the classification task has
classifier is used to classify unlabeled examples in the first different characteristics. In this section, we summarize and
round. Then, an Expectation-Maximization (EM) process compare major methods applied in several application do-
is utilized to adjust the parameters of the Naive Bayes clas- mains.
sifier and re-classify the unlabeled data in an iteration. The
process terminates when the classification result is stable. 4.1 Genomic Data
One document may belong to several categories and have In recent years, a large amount of DNA and protein se-
multiple labels. quences are available in public databases, such as GenBank [3],
Besides text classification, Zhong et al. [66] propose a HMM EMBL Nucleotide Sequence Database [1] and the Entrez
based semi-supervised classification for time series data. The protein database [2]. To understand the functions of differ-
method uses labeled data to train the initial parameters of a ent genes and proteins, sequence classification has attracted
first order HMM, and then uses unlabeled data to adjust the a lot of attention in genomic research.
model in an EM process. Wei et al. [59] adopt one nearest Feature based methods are widely used for genomic sequence
neighbor classifier for semi-supervised time series classifica- classification [35; 12; 13; 52]. k-grams [35; 36; 12] and pat-
tion. The method is designed to handle the situation where tern based feature selection [52] have been used on genomic

SIGKDD Explorations Volume 12, Issue 1

 sequences. After obtaining features, conventional classifiers, a matrix. Li et al. [31] propose a method to transform a
such as SVM [35; 36; 52], rule based classifier [5] and neural multivariate time series into a vector through singular value
networks [10] can be applied to classify genomic sequences. decomposition and other transformations. SVM is then used
To measure the distance between two genomic sequences, to classify the vectors.
global alignment and local alignment are widely used meth-
ods [32; 45]. After obtaining the distance function, KNN 4.3 Text Data
classifier can be used for genomic sequence classification [13]. Sequence classification is also widely used in information re-
By using a local alignment kernel [49], SVM can also be used trieval to categorize text and documents. The widely used
to classify protein sequences without feature selection. methods for document classification include Naive Bayes [29]
Model based methods, such as profile HMM [56], are also and SVM [43]. Text classification has various extensions
important methods for genomic sequence classification. such as multi-label text classification [67], hierarchical text
Deshpande et al. [13] compare the performance of SVM, classification [57] and semi-supervised text classification [46].
HMM, and KNN methods for classifying genomic sequence Sebastiani et al. [51] provide a more detailed survey on text
data. They find that SVM outperforms in most cases and classification .
feature selection plays an important role in determining ac-
curacies of SVM classifiers. She et al. [52] also conclude that 5. CONCLUSION
SVM is the most effective method for protein classification. In this paper, we provide a brief survey on sequence clas-
Besides accuracy, other challenges in genomic sequence clas- sification. We categorize sequence data into five subtypes.
sification are to speed up classification in order to handling We group sequence classification methods in feature based
a large amount of data [55] and to train an interpretable methods, sequence distance based methods and model based
classifier to gain knowledge about characteristics of genomic methods. We also present several extensions of the conven-
sequences [54]. tional sequence classification. At last, we compare sequence
4.2 Time Series Data classification methods applied in different application do-
mains.
Time series data is an important type of sequence data. In
We notice that most of the works focus on the classification
Time Series Data Library [4], time series data across 22 do-
task on simple symbolic sequences and simple time series
mains, such as agriculture, chemistry, health, finance,industry,
data. Although there are a few works on multiple variate
are collected. UCR time series data archive [27] provides a
time series and complex symbolic sequences, the problem
set of time series datasets as a benchmark for evaluating
of classifying complex sequence data is still open at large.
time series classification methods.
Furthermore, most of the methods are devoted to the con-
For simple time series data, to apply feature based methods,
ventional sequence classification task. Streaming sequence
the feature selection is a challenging task since we cannot do
classification, early classification, semi-supervised classifica-
feature enumeration on numeric data. Therefore, distance
tion on sequence data and the combinations of those prob-
based methods are widely adopted to classify time series [61;
lems on complex sequence data which have practical appli-
26; 59; 48]. It is shown that comparing to a wide range
cations, present challenges for future studies.
of classifiers, such as neural networks, SVM and HMM, 1-
nearest neighbor classifier with dynamic time warping dis-
tance is usually superior in classification accuracy [61]. 6. REFERENCES
To apply feature based methods on simple time series, usu-
ally, before feature selection, time series data needs to be [1] Embl nucleotide sequence database homepage: http:
transformed into symbolic sequences through discretization //[Link]/embl/.
or symbolic transformation [40]. Without discretization, Ye
et al. [65] propose a method to find time series shapelets [2] Entrez protein database homepage: [Link]
and use a decision tree to classify time series. Comparing to [Link]/sites/entrez?db=protein.
distance based methods, feature based methods may speed [3] Genbank homepage: [Link]
up the classification process and be able to generate some Genbank/.
interpretable results.
Model based methods are also applied to classify simple time [4] Time series data library webpage: http:
series, such as HMM which is widely used in speech recog- //[Link]/~hyndman/
nition [47]. TSDL/.
Multivariate time series classification has been used for ges-
[5] C. C. Aggarwal. On effective classification of strings
ture recognition [24] and motion recognition [38]. The multi-
with wavelets. In KDD ’02: Proceedings of the eighth
variate data is generated by a set of sensors which measure
ACM SIGKDD international conference on Knowledge
the movements of objects in different locations and direc-
discovery and data mining, pages 163–172, 2002.
tions. For multivariate time series classification, Kadous et
al. [24] propose a feature based classifier. A set of user- [6] S. F. Altschul, W. Gish, W. Miller, E. W. Myers,
defined meta-features are constructed and a multivariate and D. J. Lipmanl. Basic local alignment search tool.
time series is transformed into a feature vector. Some uni- [Link]., 215:403–410, 1990.
versal meta-features include the features to describe the
trends of increases and decreases and local max or min val- [7] Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden
ues. By using those features, multivariate time series with markov support vector machines. In ICML ’03: The
additional non-temporal attributes can be classified by a de- Twentieth International Conference on Machine Learn-
cision tree. One multivairate time series can be viewed as ing, pages 3–10, 2003.

SIGKDD Explorations Volume 12, Issue 1

 [8] B. Anibal, S. M. Aranzazu, and R. J. Jose. Early fault [22] X. Ji, J. Bailey, and G. Dong. Mining minimal dis-
classification in dynamic systems using case-based rea- tinguishing subsequence patterns with gap constraints.
soning. Lecture notes in computer science, 4177:211– Knowl. Inf. Syst., 11(3):259–286, 2007.
220, 2005.
[23] M. W. Kadous. Temporal classification: extending the
[9] L. Bernaille, R. Teixeira, I. Akodkenou, A. Soule, and classification paradigm to multivariate time series. PhD
K. Salamatian. Traffic classification on the fly. Com- thesis, 2002.
puter Communication Review, 36(2):23–26, 2006.
[24] M. W. Kadous and C. Sammut. Classification of mul-
[10] K. Blekas, D. I. Fotiadis, and A. Likas. Motif-based tivariate time series and structured data using con-
protein sequence classification using neural networks. structive induction. Machine Learning, 58(2-3):179–
Journal of Computational Biology, 12(1):64–82, 2005. 216, 2005.
[11] B. Cheng, J. Carbonell, and [Link]-Seetharaman. Pro- [25] L. Kaján, A. Kertész-Farkas, D. Franklin, N. Ivanova,
tein classification based on text document classification A. Kocsor, and S. Pongor. Application of a simple like-
techniques. Proteins, 1(58):855–970, 2005. lihood ratio approximant to protein sequence classifica-
tion. Bioinformatics, 22(23):2865–2869, 2006.
[12] N. A. Chuzhanova, A. J. Jones, and S. Margetts. Fea-
ture selection for genetic sequence classification. Bioin- [26] E. Keogh and S. Kasetty. On the need for time se-
formatics, 14(2):139–143, 1998. ries data mining benchmarks: a survey and empirical
demonstration. In KDD ’02: Proceedings of the eighth
[13] M. Deshpande and G. Karypis. Evaluation of tech-
ACM SIGKDD international conference on Knowledge
niques for classifying biological sequences. In PAKDD
discovery and data mining, pages 102–111, 2002.
’02: Proceedings of the 6th Pacific-Asia Conference on
Advances in Knowledge Discovery and Data Mining, [27] E. Keogh, X. Xi, L. Wei, and C. A. Ratanama-
pages 417–431, 2002. hatana. The UCR time series classification and clus-
tering homepage: [Link]
[14] J. J. R. Diez, C. A. González, and H. Boström. Boosting
time_series_data/, 2006.
interval based literals. Intell. Data Anal., 5(3):245–262,
2001. [28] E. J. Keogh and M. J. Pazzani. Scaling up dynamic
[15] H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, time warping for datamining applications. In KDD ’00:
and E. J. Keogh. Querying and mining of time series Proceedings of the sixth ACM SIGKDD international
data: experimental comparison of representations and conference on Knowledge discovery and data mining,
distance measures. PVLDB, 1(2):1542–1552, 2008. pages 285–289, 2000.

[16] G. Dong and P. Jian. Sequence Data Mining, pages 47– [29] S.-B. Kim, K.-S. Han, H.-C. Rim, and S. H. Myaeng.
65. Springer US, 2007. Some effective techniques for naive bayes text classi-
fication. IEEE Transactions on Knowledge and Data
[17] R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchison. Engineering, 18(11):1457–1466, Nov. 2006.
Chapter 3. Markov Chain and Hidden Markov Model.
Biological Sequence Analysis: Probabilistic Models of [30] D. Kudenko and H. Hirsh. Feature generation for se-
Proteins and Nucleic Acids, pages 47–65. Cambridge quence categorization. In AAAI ’98/IAAI ’98: Pro-
University Press, 1998. ceedings of the fifteenth national/tenth conference on
Artificial intelligence/Innovative applications of artifi-
[18] O. Duskin and D. G. Feitelson. Distinguishing humans cial intelligence, pages 733–738, 1998.
from robots in web search logs: preliminary results us-
ing query rates and intervals. In WSCD09: Proceedings [31] J. D. Lafferty, A. McCallum, and F. C. N. Pereira.
of the 2009 workshop on Web Search Click Data, pages Conditional random fields: Probabilistic models for seg-
15–19, 2009. menting and labeling sequence data. In ICML ’01: Pro-
ceedings of the Eighteenth International Conference on
[19] Y. Freund and R. E. Schapire. A decision-theoretic gen- Machine Learning, pages 282–289, 2001.
eralization of on-line learning and an application to
boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997. [32] T. W. Lam, W.-K. Sung, S.-L. Tam, C.-K. Wong, and
S.-M. Yiu. Compressed indexing and local alignment of
[20] A. Graves, S. Fernández, F. Gomez, and J. Schmid- DNA. Bioinformatics, 24(6):791–797, 2008.
huber. Connectionist temporal classification: labelling
unsegmented sequence data with recurrent neural net- [33] T. Lane and C. E. Brodley. Temporal sequence learning
works. In ICML ’06: Proceedings of the 23rd interna- and data reduction for anomaly detection. ACM Trans.
tional conference on Machine learning, pages 369–376, Inf. Syst. Secur., 2(3):295–331, 1999.
2006.
[34] N. Lesh, M. J. Zaki, and M. Ogihara. Mining features
[21] M. P. Griffin and J. R. Moorman. Toward the early for sequence classification. In KDD ’99: Proceedings
diagnosis of neonatal sepsis and sepsis-like illness us- of the fifth ACM SIGKDD international conference on
ing novel heart rate analysis. PEDIATRICS, 107(1):97– Knowledge discovery and data mining, pages 342–346,
104, 2001. 1999.

SIGKDD Explorations Volume 12, Issue 1

 [35] C. S. Leslie, E. Eskin, and W. S. Noble. The spectrum [50] B. Schölkopf, K. Tsuda, and J.-P. Vert. Kernel Meth-
kernel: A string kernel for SVM protein classification. ods in Computational Biology, pages 171–192. The MIT
In Pacific Symposium on Biocomputing, pages 566–575, press, 2004.
2002.
[51] F. Sebastiani. Machine learning in automated text cat-
[36] C. S. Leslie and R. Kuang. Fast string kernels using egorization. ACM Comput. Surv., 34(1):1–47, 2002.
inexact matching for protein sequences. Journal of Ma-
chine Learning Research, 5:1435–1455, 2004. [52] R. She, F. Chen, K. Wang, M. Ester, J. L. Gardy, and
F. S. L. Brinkman. Frequent-subsequence-based predic-
[37] D. D. Lewis. Naive (bayes) at forty: The independence tion of outer membrane proteins. In KDD ’03: Proceed-
assumption in information retrieval. In ECML’ 98: The ings of the ninth ACM SIGKDD international confer-
10th European Conference on Machine Learning, pages ence on Knowledge discovery and data mining, pages
4–15, 1998. 436–445, 2003.
[38] C. Li, L. Khan, and B. Prabhakaran. Real-time clas- [53] T. Smith and M. Waterman. Identification of com-
sification of variable length multi-attribute motions. mon molecular subsequences. [Link]., 147:195–197,
Knowl. Inf. Syst., 10(2):163–183, 2006. 1981.
[39] M. Li and R. Sleep. A robust approach to sequence [54] S. Sonnenburg, G. Rätsch, and C. Schäfer. Learning
classification. In ICTAI ’05: Proceedings of the 17th interpretable SVMs for biological sequence classifica-
IEEE International Conference on Tools with Artificial tion. In RECOMB ’05: The Ninth Annual International
Intelligence, pages 197–201, 2005. Conference on Research in Computational Molecular
Biology, pages 389–407, 2005.
[40] J. Lin, E. J. Keogh, L. Wei, and S. Lonardi. Experienc-
ing SAX: a novel symbolic representation of time series. [55] S. Sonnenburg, G. Rätsch, and B. Schölkopf. Large
Data Min. Knowl. Discov., 15(2):107–144, 2007. scale genomic sequence svm classifiers. In ICML ’05:
[41] N. Littlestone. Learning quickly when irrelevant at- Proceedings of the 22nd international conference on
tributes abound: A new linear-threshold algorithm. Machine learning, pages 848–855, 2005.
Machine Learning, 2(4):285–318, 1987. [56] P. K. Srivastava, D. K. Desai, S. Nandi, and A. M.
[42] X. Liu, P. Zhang, and D. Zeng. Sequence matching for Lynn. HMM-ModE-Improved classification using pro-
suspicious activity detection in anti-money laundering. file hidden Markov models by optimising the discrim-
In PAISI, PACCF and SOCO ’08: Proceedings of the ination threshold and modifying emission probabilities
IEEE ISI 2008 PAISI, PACCF, and SOCO interna- with negative training sequences. BMC Bioinformatics,
tional workshops on Intelligence and Security Informat- 8(104), 2007.
ics, pages 50–61, 2008. [57] A. Sun and E.-P. Lim. Hierarchical text classification
[43] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and evaluation. In ICDM, pages 521–528, 2001.
and C. J. C. H. Watkins. Text classification using string [58] P.-N. Tan and V. Kumar. Discovery of web robot ses-
kernels. Journal of Machine Learning Research, 2:419– sions based on their navigational patterns. Data Min.
444, 2002. Knowl. Discov., 6(1):9–35, 2002.
[44] S. Needleman and C. Wunsch. A general method ap-
[59] L. Wei and E. Keogh. Semi-supervised time series clas-
plicable to the search for similarities in the amino acid
sification. In KDD ’06: Proceedings of the 12th ACM
sequence of two proteins. [Link]., 48:443–453, 1970.
SIGKDD international conference on Knowledge dis-
[45] L. A. Newberg. Memory-efficient dynamic program- covery and data mining, pages 748–753, 2006.
ming backtrace and pairwise local sequence alignment.
[60] J. Weston, C. S. Leslie, D. Zhou, A. Elisseeff, and W. S.
Bioinformatics, 24(16):1772–1778, 2008.
Noble. Semi-supervised protein classification using clus-
[46] K. Nigam, A. McCallum, S. Thrun, and T. M. Mitchell. ter kernels. In NIPS, 2003.
Text classification from labeled and unlabeled docu-
ments using EM. Machine Learning, 39(2/3):103–134, [61] X. Xi, E. Keogh, C. Shelton, L. Wei, and C. A.
2000. Ratanamahatana. Fast time series classification using
numerosity reduction. In ICML ’06: Proceedings of
[47] L. Rabiner. A tutorial on HMM and selected applica- the 23rd international conference on Machine learning,
tions in speech recognition. In IEEE, pages 257–286, pages 1033–1040, 2006.
1998.
[62] Z. Xing, J. Pei, G. Dong, and P. S. Yu. Mining sequence
[48] C. A. Ratanamahatana and E. J. Keogh. Making time- classifiers for early prediction. In SDM’08: Proceedings
series classification more accurate using learned con- of the 2008 SIAM international conference on data min-
straints. In SDM ’04: SIAM International Conference ing, pages 644–655, 2008.
on Data Mining, 2004.
[63] Z. Xing, J. Pei, and P. S. Yu. Early classification on
[49] H. Saigo, J.-P. Vert, N. Ueda, and T. Akutsu. Pro- time series: A nearest neighbor approach. In IJCAI’09:
tein homology detection using string alignment kernels. Proceedings of the 21st International Joint Conference
Bioinformatics, 20(11):1682–1689, 2004. on Artificial Intelligence, pages 1297–1302, 2009.

SIGKDD Explorations Volume 12, Issue 1

 [64] O. Yakhnenko, A. Silvescu, and V. Honavar. Discrimi-
natively trained markov model for sequence classifica-
tion. In ICDM ’05: Proceedings of the Fifth IEEE In-
ternational Conference on Data Mining, pages 498–505,
2005.
[65] L. Ye and E. Keogh. Time series shapeletes: A new
primitive for data mining. In KDD ’09: Proceedings
of the 15th ACM SIGKDD international conference on
Knowledge discovery and data mining, 2009.
[66] S. Zhong. Semi-supervised sequence classification with
Hmms. IJPRAI, 19(2):165–182, 2005.
[67] S. Zhu, X. Ji, W. Xu, and Y. Gong. Multi-labelled clas-
sification using maximum entropy method. In SIGIR,
pages 274–281, 2005.

SIGKDD Explorations Volume 12, Issue 1