Local decoding of sequences and alignment-free comparison.
Subword composition plays an important role in a lot of analyses of sequences. Here we define and study the "local decoding of order N of sequences," an alternative that avoids some drawbacks of "subwords of length N" approaches while keeping informations about environments of length N in the sequences ("decoding" is taken here in the sense of hidden Markov modeling, i.e., associating some state to all positions of the sequence). We present an algorithm for computing the local decoding of order N of a given set of sequences. Its complexity is linear in the total length of the set (whatever the order N) both in time and memory space. In order to show a use of local decoding, we propose a very basic dissimilarity measure between sequences which can be computed both from local decoding of order N and composition in subwords of length N. The accuracies of these two dissimilarities are evaluated, over several datasets, by computing their linear correlations with a reference alignment-based distance. These accuracies are also compared to the one obtained from another recent alignment-free comparison.
Didier
Gilles
G
Institut de Mathématiques de Luminy, UMR 6206, Campus de Luminay, Case 907, 13288 Marseille, France. didier@iml.univ-mrs.fr
Laprevotte
Ivan
I
Pupin
Maude
M
Hénaut
Alain
A
D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D016415:Sequence Alignment; D017421:Sequence Analysis / Q000379:methods*