  The major problem of fitting a higher order Markov model is the exponentially
growing number of parameters. The most popular approach is to use a Variable
Length Markov Chain (VLMC), which determines relevant contexts (recent pasts)
of variable orders and form a context tree. A more general approach is called
Sparse Markov Model (SMM), where all possible histories of order $m$ form a
partition so that the transition probability vectors are identical for the
histories belonging to a particular group. We develop an elegant method of
fitting SMM using convex clustering, which involves regularization. The
regularization parameter is selected using BIC criterion. Theoretical results
demonstrate the model selection consistency of our method for large sample
size. Extensive simulation studies under different set-up have been presented
to measure the performance of our method. We apply this method to classify
genome sequences, obtained from individuals affected by different viruses.
