MS4--Multi-Scale Selector of Sequence Signatures: an alignment-free method for classification of biological sequences

• Published in: BMC bioinformatics 2010-07, Vol.11 (1), p.406-406, Article 406
• Main Authors: Corel, Eduardo, Pitschi, Florian, Laprevotte, Ivan, Grasseau, Gilles, Didier, Gilles, Devauchelle, Claudine
• Format: Article
• Language: English
• Subjects: Algorithms; Amino Acid Sequence; Applications software; Base Sequence; Classification - methods; Computational biology; Computational Biology - methods; DNA sequencing; Genes, nef; Genome, Viral; HIV - classification; HIV - genetics; HIV Long Terminal Repeat; Human immunodeficiency virus; Life Sciences; Nucleotide sequencing; Quantitative Methods; Simian immunodeficiency virus; Simian Immunodeficiency Virus - classification; Simian Immunodeficiency Virus - genetics; Software
• ISSN: 1471-2105; 1471-2105
• DOI: 10.1186/1471-2105-11-406

While multiple alignment is the first step of usual classification schemes for biological sequences, alignment-free methods are being increasingly used as alternatives when multiple alignments fail. Subword-based combinatorial methods are popular for their low algorithmic complexity (suffix trees ...) or exhaustivity (motif search), in general with fixed length word and/or number of mismatches. We developed previously a method to detect local similarities (the N-local decoding) based on the occurrences of repeated subwords of fixed length, which does not impose a fixed number of mismatches. The resulting similarities are, for some "good" values of N, sufficiently relevant to form the basis of a reliable alignment-free classification. The aim of this paper is to develop a method that uses the similarities detected by N-local decoding while not imposing a fixed value of N. We present a procedure that selects for every position in the sequences an adaptive value of N, and we implement it as the MS4 classification tool. Among the equivalence classes produced by the N-local decodings for all N, we select a (relatively) small number of "relevant" classes corresponding to variable length subwords that carry enough information to perform the classification. The parameter N, for which correct values are data-dependent and thus hard to guess, is here replaced by the average repetitivity kappa of the sequences. We show that our approach yields classifications of several sets of HIV/SIV sequences that agree with the accepted taxonomy, even on usually discarded repetitive regions (like the non-coding part of LTR). The method MS4 satisfactorily classifies a set of sequences that are notoriously hard to align. This suggests that our approach forms the basis of a reliable alignment-free classification tool. The only parameter kappa of MS4 seems to give reasonable results even for its default value, which can be a great advantage for sequence sets for which little information is available.