Simultaneous Detection and Discrimination of Subsequences Which Are Nonlinearly Extended Elements of the Given Sequences Alphabet in a Quasiperiodic Sequence

摘要

We consider a posteriori approach to the problem of noise-proof simultaneous detection and discrimination of subsequences-fragments having some given properties in a quasiperiodic sequence. The solution to the problem is stated for the case when the quantity of sought subsequences is unknown. We assume that 1) a finite alphabet of reference sequences is given; 2) a set of permissible deformations is defined for the alphabet, this set gathers all possible extensions of its elements (by duplicating their components); 3) every subsequence-fragment in the quasiperiodic sequence belongs to the set of permissible deformations; 4) subsequences-fragments do not intersect each other, and the difference between the initial positions of two neighboring fragments is limited from above by a given value. We show that in the framework of a posteriori approach, the problem of simultaneous detection and discrimination reduces to solving an unexplored discrete optimization problem. A polynomial-time algorithm that guarantees the optimal solution to this optimization problem is proposed. The results of the numerical simulation are presented.