Abstract  Following recent discoveries about the important roles of non-coding RNAs (ncRNAs) in the cellular machinery, there is now great interest in identifying new occurrences of ncRNAs in available genomic sequences. In this paper, we show how the problem of finding new occurrences of characterized ncRNAs can be modeled as the problem of finding all locally-optimal solutions of a weighted constraint network using dedicated weighted global constraints, encapsulating pattern-matching algorithms and data structures. This is embodied in DARN!, a software tool for ncRNA localization, which, compared to existing pattern-matching based tools, offers additional expressivity (such as enabling RNA–RNA interactions to be described) and improved specificity (through the exploitation of scores and local optimality) without compromises in CPU efficiency. This is demonstrated on the actual search for tRNAs and H/ACA sRNA on different genomes.