An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences

Details An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences

2011-02-27

arxiv.org/abs/1102.5482v14

Computer Science

Information Theory

Scientific paper

One of the central problems in phylogenetic analysis. is that of checking the similarity of a sample test sequence against a training sequence (which in many cases is much longer than the test sequence) which contains specific features that are sought of in the test sequence. Some popular classification algorithms adopt a probabilistic approach, by assuming that the sequences are realizations of some variable-length Markov process or a hidden Markov process (HMM), thus enabling the imbedding of the training data in a variable-length suffix tree, the size of which is usually linear in N, the length of the test sequence. An axiomatic approach to the notion of similarity of sequences cases is proposed. Despite of the fact that it is not assumed that the sequences are a realization of a probabilistic process (an assumption that does not seem to be fully justified when dealing with biological data), it is demonstrated that any classifier that fully complies with the proposed similarity axioms may, without any loss in generality, always be based on presenting the training data that is contained in a (long) individual training sequence via a suffix tree with no more than O(N) leaves (or, alternatively, a table with O(N) entries), regardless of how long the training sequence is. Furthermore, the generation algorithm of the suffix tree from the training sequence is universal, and does not depend on the specific features that are imbedded in the training data. As an example, a published universal classification algorithm is shown to comply with the proposed axiomatic conditions and the resulting organization of the training data, yielding a formal axiomatic justification (as well as a classical probabilistic justification) for its good empirical results without relying on any a-priori probabilistic assumptions..

Affiliated with

Also associated with

No associations

Rating

An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Axiomatic, Non-Probabilistic Approach to Classification of Individual Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53932