Pattern Matching of Positive and Negative DNA Sequences with General Gaps and One-off Constraints
摘要
The symmetrical DNA double-helix structure stores a large amount of complex and valuable biological information. Pattern matching of DNA sequence can count the location and number of gene fragments, which is beneficial to state tracking and targeted therapy of pathogenic genes. However, most sequence pattern matching methods target the entire sequence rather than frequent sequence patterns, which increase the computational complexity. In addition, current research methods ignore gene fragments with missing bases, and there is no unified analysis method for negative sequence pattern. In this case, the accuracy and efficiency of biological information analysis is significantly influenced. In view of the low efficiency and the small number of DNA sequence matching the paths obtained in the existing analysis methods, in this paper, we propose a method for pattern matching of positive and negative DNA sequences with general gaps and one-off constraints. First of all, the mined frequent sequence patterns are taken as patterns in the matching process, in order to make pattern matching more practical. Additionally, the negative sequences are used as pattern P for pattern matching, and reasonable gaps are inserted to make the matching process more flexible. Then, a detection mechanism for two duplicate elements is proposed, which not only effectively prunes the matching paths that do not meet the one-off constraint, but also accurately matches all information and eliminates redundancy. Experiments on the DNA sequences of 10 real species show that the algorithm can effectively deal with negative sequence patterns and obtain more matching paths, with the running efficiency to be improved.