Mönstermatchning är en nyckelfråga i sekventiell mönsterbrytning. Många forskare fokuserar nu på mönstermatchning med gapbegränsningar. De flesta av dessa studier omfattar dock exakta mönstermatchningsproblem, ett speciellt fall av ungefärlig mönstermatchning och en mer utmanande uppgift. I denna studie introducerar vi ett ungefärligt mönster matchande problem med Hamming avstånd. Dess mål är att beräkna antalet ungefärliga förekomster av mönster P med gap begränsningar i sekvens S under likhet begränsning d. Vi föreslår en effektiv algoritm som heter Single-rOot Nettree för ungefärliga mönster matchinG med gap begränsningar (SONG) baserat på en ny icke-linjär datastruktur Single-root Nettree för att effektivt lösa problemet. Teoretisk analys och experiment visar en intressant lag att förhållandet M(P,S,d)/N(P,S,m) ungefär följer en binomial fördelning, där M (P,S,d) och N(P,S,m) är antalet ungefärliga händelser vars avstånd till mönster P är d (0≤d≤m) respektive inte mer än m (längden på mönster P). Experimentella resultat för verkliga biologiska data validerar SONG:s effektivitet och effektivitet.
Det finns två typer av mönster matchning med gap begränsningar: traditionella mönster matchning och strikt mönster matchande REF.
Approximate pattern matching with gap constraints
{'venue': 'J. Inf. Sci.', 'journal': 'J. Inf. Sci.', 'mag_field_of_study': ['Computer Science']}