Structured motifs search.
In this paper, we describe an algorithm for the localization of structured models, i.e. sequences of (simple) motifs and distance constraints. It basically combines standard pattern matching procedures with a constraint satisfaction solver, and it has the ability, not present in similar tools, to search for partial matches. A significant feature of our approach, especially in terms of efficiency for the application context, is that the (potentially) exponentially many solutions to the considered problem are represented in compact form as a graph. Moreover, the time and space necessary to build the graph are linear in the number of occurrences of the component patterns.
Morgante
Michele
M
Department of Crop Sciences and Agricultural Engineering, via delle Scienze 206, 33100 Udine, Italy.
Policriti
Alberto
A
Vitacolonna
Nicola
N
Zuccolo
Andrea
A
D000465:Algorithms; D001483:Base Sequence; D016000:Cluster Analysis; D019295:Computational Biology; D004251:DNA Transposable Elements / Q000235:genetics; D016678:Genome; D016247:Information Storage and Retrieval; D008957:Models, Genetic; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012984:Software
D004251:DNA Transposable Elements