title: Structured motifs search.
abstract: 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.
authors.affiliation: Department of Crop Sciences and Agricultural Engineering, via delle Scienze 206, 33100 Udine, Italy.
authors.forename: Michele
authors.initials: M
authors.lastname: Morgante
authors.forename: Alberto
authors.initials: A
authors.lastname: Policriti
authors.forename: Nicola
authors.initials: N
authors.lastname: Vitacolonna
authors.forename: Andrea
authors.initials: A
authors.lastname: Zuccolo
mesh_terms: 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
chemical_list: D004251:DNA Transposable Elements