Página 1 dos resultados de 1804 itens digitais encontrados em 0.013 segundos

GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences

Deusdado, Sérgio; Carvalho, Paulo
Fonte: Inderscience Publishers Publicador: Inderscience Publishers
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
57.107173%
In this paper, we propose Genomic-oriented Rapid Algorithm for String Pattern-match (GRASPm), an algorithm centred on overlapped 2-grams analysis, which introduces a novel filtering heuristic – the compatibility rule – achieving significant efficiency gain. GRASPm’s foundations rely especially on a wide searching window having the central duplet as reference for fast filtering of multiple alignments. Subsequently, superfluous detailed verifications are summarily avoided by filtering the incompatible alignments using the idcd (involving duplet of central duplet) concept combined with pre-processed conditions, allowing fast parallel testing for multiple alignments. Comparative performance analysis, using diverse genomic data, shows that GRASPm is faster than its competitors.

Efficient exact pattern-matching in proteomic sequences

Deusdado, Sérgio; Carvalho, Paulo
Fonte: Springer-Verlag Publicador: Springer-Verlag
Tipo: Parte de Livro
Português
Relevância na Pesquisa
57.107173%
This paper proposes a novel algorithm for complete exact pattern-matching focusing the specificities of protein sequences (alphabet of 20 symbols) but, also highly efficient considering larger alphabets. The searching strategy uses large search windows allowing multiple alignments per iteration. A new filtering heuristic, named compatibility rule, contributed decisively to the efficiency improvement. The new algorithm’s performance is, on average, superior in comparison with its best-rated competitors.

DC: a highly efficient and flexible exact pattern-matching algorithm

Deusdado, Sérgio; Carvalho, Paulo
Fonte: Centro de Ciências e Tecnologias da Computação - Universidade do Minho Publicador: Centro de Ciências e Tecnologias da Computação - Universidade do Minho
Tipo: Relatório
Português
Relevância na Pesquisa
67.430503%
ware of the need for faster and flexible searching algorithms in fields such as web searching or bioinformatics, we propose DC - a high-performance algorithm for exact pattern matching. Emphasizing the analysis of pattern peculiarities in the pre-processing phase, the algorithm en- compasses a novel search logic based on the examination of multiple alignments within a larger window, selectively tested after a powerful heuristic called compatibility rule is verified. The new algorithm’s performance is, on average, above its best-rated competitors when testing different data types and using a complete suite of pattern extensions and compositions. The flexibility is remarkable and the efficiency is more relevant in quaternary or greater alphabets. Keywords: exact pattern-match, searching algorithms.

Métodos eficientes para a detecção de padrões exactos (pattern-matching) em sequências biológicas

Deusdado, Sérgio
Fonte: Instituto Politécnico de Bragança. Escola Superior de Tecnologia e Gestão Publicador: Instituto Politécnico de Bragança. Escola Superior de Tecnologia e Gestão
Tipo: Conferência ou Objeto de Conferência
Português
Relevância na Pesquisa
67.449316%
Os algoritmos de detecção de padrões (pattern-matching), sejam exactos ou aproximados, são fundamentais na maioria das aplicações orientadas à análise de sequências biológicas. Nesta comunicação apresenta-se um novo algoritmo, denominado DC, desenvolvido para a especificidade do pattern-matching exacto, bem como uma análise comparativa do seu desempenho. Conclui-se que o desempenho do novo algoritmo supera, em média, o dos seus concorrentes, atribuindo-se o ganho de eficiência, sobretudo, à introdução de uma nova regra de filtragem denominada regra de compatibilidade.

Graphical models and point set matching; Modelos Gráficos e Casamento de Padrões de Pontos

Caetano, Tiberio Silva
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Tese de Doutorado Formato: application/pdf
Português
Relevância na Pesquisa
57.817686%
Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise...

Graphical models and point pattern matching

Caetano, Tiberio Silva; Caelli, Terry; Schuurmans, Dale; Barone, Dante Augusto Couto
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Artigo de Revista Científica Formato: application/pdf
Português
Relevância na Pesquisa
67.680815%
This paper describes a novel solution to the rigid point pattern matching problem in Euclidean spaces of any dimension. Although we assume rigid motion, jitter is allowed. We present a noniterative, polynomial time algorithm that is guaranteed to find an optimal solution for the noiseless case. First, we model point pattern matching as a weighted graph matching problem, where weights correspond to Euclidean distances between nodes. We then formulate graph matching as a problem of finding a maximum probability configuration in a graphical model By using graph rigidity arguments, we prove that a sparse graphical model yields equivalent results to the fully connected model in the noiseless case. This allows us to obtain an algorithm that runs in polynomial time and is provably optimal for exact matching between noiseless point sets. For inexact matching, we can still apply the same algorithm to find approximately optimal solutions. Experimental results obtained by our approach show improvements in accuracy over current methods, particularly when matching patterns of different sizes.

Efficient exact pattern-matching in proteomic sequences

Deusdado, Sérgio; Carvalho, Paulo
Fonte: Springer Publicador: Springer
Tipo: Artigo de Revista Científica
Publicado em /06/2009 Português
Relevância na Pesquisa
67.274365%
http://www.informatik.uni-trier.de/%7Eley/db/conf/iwpacbb/iwpacbb2009.html; This paper proposes a novel algorithm for complete exact pattern-matching focusing the specificities of protein sequences (alphabet of 20 symbols) but, also highly efficient considering larger alphabets. The searching strategy uses large search windows allowing multiple alignments per iteration. A new filtering heuristic, named compatibility rule, contributed decisively to the efficiency improvement. The new algorithm’s performance is, on average, superior in comparison with its best-rated competitors.

The Lymphocyte Pattern Matching Engine

Miller, Bradford W.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
67.274365%
This document describes a new pattern matching engine used as part of the discourse reasoning components in the TRAINS-96 system. Its dominant characteristics are simplicity, efficiency, and an economical model for driving the search engine.

A comparison of personal name matching: Techniques and practical issues

Christen, Peter
Fonte: ANU Department of Computer Science / Computer Sciences Laboratory Publicador: ANU Department of Computer Science / Computer Sciences Laboratory
Tipo: Working/Technical Paper
Português
Relevância na Pesquisa
57.47198%
Finding and matching personal names is at the core of an increasing number of applications: from text and Web mining, information retrieval and extraction, search engines, to deduplication and data linkage systems. Variations and errors in names make exact string matching problematic, and approximate matching techniques based on phonetic encoding or pattern matching have to be applied. When compared to general text, however, personal names have different characteristics that need to be considered. ¶ In this paper we discuss the characteristics of personal names and present potential sources of variations and errors. We overview a comprehensive number of commonly used, as well as some recently developed name matching techniques. Experimental comparisons on four large name data sets indicate that there is no clear best technique. We provide a series of recommendations that will help researchers and practitioners to select a name matching technique suitable for a given data set.; no

Higher-order associative commutative pattern matching for component retrieval

Hemer, D.
Fonte: Elsevier BV Publicador: Elsevier BV
Tipo: Artigo de Revista Científica
Publicado em //2004 Português
Relevância na Pesquisa
57.565137%
In this paper we describe a higher-order associative commutative pattern matching algorithm. We are motivated by the need for developing tool support for matching user requirements against library component interfaces, both specified using a formal language. In developing such tool support we aim for a maximum level of recall, while at the same time maintaining a reasonable level of automation and effciency. In order to support adaptation of library components we assume the library components may contain higher-order parameters (representing types, functions and relations) – components are adapted by instantiating parameters to suit the requirements of the user. However with this assumption, the usual specification matching techniques, based on proving equivalence using a theorem prover based on first-order logic, are no longer useful in general. We therefore propose building tool support based on pattern matching, and increasing recall by providing (partial) support for matching expressions that can be shown to be equivalent by applying the laws of associativity and commutativity.; http://www.elsevier.com/wps/find/journaldescription.cws_home/681021/description#description; Proceedings of Computing: The Australasian Theory Symposium (CATS) 2004

Integrated Memristor-MOS (M²) sensor for basic pattern matching applications; Integrated Memristor-MOS (M(2)) sensor for basic pattern matching applications

Kavehei, O.; Cho, K.R.; Lee, S.; Al-Sarawi, S.; Eshraghian, K.; Abbott, D.
Fonte: American Scientific Publishers Publicador: American Scientific Publishers
Tipo: Artigo de Revista Científica
Publicado em //2013 Português
Relevância na Pesquisa
67.569355%
This paper introduces an integrated sensor circuit based on an analog Memristor-MOS (M2) pattern matching building block that calculates the similarity/dissimilarity between two analog values. A new approach for a pulse-width modulation pixel image sensor compatible with the memristive-MOS matching structure is introduced allowing direct comparison between incoming and stored images. The pulsed-width encoded information from the pixels is forwarded to a matching circuitry that provides an anti-Gaussian-like comparison between the states of memristors. The non-volatile and multi-state memory characteristics of memristor, together with the related ability to be programmed at any one of the intermediate states between logic '1' and logic '0' brings us closer to the implementation of bio-machines that can eventually emulate human-like sensory functions.; Omid Kavehei, Kyoung-Rok Cho, Sang-Jin Lee, Said Al-Sarawi, Kamran Eshraghian, and Derek Abbott

Pattern Discovery in Protein Structures and Interaction Networks

Ahmed, Hazem Radwan A.
Fonte: Quens University Publicador: Quens University
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
57.45716%
Pattern discovery in protein structures is a fundamental task in computational biology, with important applications in protein structure prediction, profiling and alignment. We propose a novel approach for pattern discovery in protein structures using Particle Swarm-based flying windows over potentially promising regions of the search space. Using a heuristic search, based on Particle Swarm Optimization (PSO) is, however, easily trapped in local optima due to the sparse nature of the problem search space. Thus, we introduce a novel fitness-based stagnation detection technique that effectively and efficiently restarts the search process to escape potential local optima. The proposed fitness-based method significantly outperforms the commonly-used distance-based method when tested on eight classical and advanced (shifted/rotated) benchmark functions, as well as on two other applications for proteomic pattern matching and discovery. The main idea is to make use of the already-calculated fitness values of swarm particles, instead of their pairwise distance values, to predict an imminent stagnation situation. That is, the proposed fitness-based method does not require any computational overhead of repeatedly calculating pairwise distances between all particles at each iteration. Moreover...

Graphical Models and Point Pattern Matching

Caetano, Tiberio; Caelli, Terry; Schuurmans, Dale; Barone, Dante
Fonte: Institute of Electrical and Electronics Engineers (IEEE Inc) Publicador: Institute of Electrical and Electronics Engineers (IEEE Inc)
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
67.449316%
This paper describes a novel solution to the rigid point pattern matching problem in Euclidean spaces of any dimension. Although we assume rigid motion, jitter is allowed. We present a noniterative, polynomial time algorithm that is guaranteed to find an

A unified formulation of invariant point pattern matching

Caetano, Tiberio; Caelli, Terry
Fonte: Institute of Electrical and Electronics Engineers (IEEE Inc) Publicador: Institute of Electrical and Electronics Engineers (IEEE Inc)
Tipo: Conference paper
Português
Relevância na Pesquisa
67.519014%
We present a unified framework for modeling and solving invariant point pattern matching problems. Invariant features are encoded as potentials in a probabilistic graphical model. By using a specific kind of graph topology, different types of invariant ma

An Efficient Approximation Algorithm for Point Pattern Matching Under Noise

Choi, Vicky; Goyal, Navin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
57.107173%
Point pattern matching problems are of fundamental importance in various areas including computer vision and structural bioinformatics. In this paper, we study one of the more general problems, known as LCP (largest common point set problem): Let $\PP$ and $\QQ$ be two point sets in $\mathbb{R}^3$, and let $\epsilon \geq 0$ be a tolerance parameter, the problem is to find a rigid motion $\mu$ that maximizes the cardinality of subset $\II$ of $Q$, such that the Hausdorff distance $\distance(\PP,\mu(\II)) \leq \epsilon$. We denote the size of the optimal solution to the above problem by $\LCP(P,Q)$. The problem is called exact-LCP for $\epsilon=0$, and \tolerant-LCP when $\epsilon>0$ and the minimum interpoint distance is greater than $2\epsilon$. A $\beta$-distance-approximation algorithm for tolerant-LCP finds a subset $I \subseteq \QQ$ such that $|I|\geq \LCP(P,Q)$ and $\distance(\PP,\mu(\II)) \leq \beta \epsilon$ for some $\beta \ge 1$. This paper has three main contributions. (1) We introduce a new algorithm, called {\DA}, which gives the fastest known deterministic 4-distance-approximation algorithm for \tolerant-LCP. (2) For the exact-LCP, when the matched set is required to be large, we give a simple sampling strategy that improves the running times of all known deterministic algorithms...

Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching

McAuley, Julian J.; Caetano, Tiberio S.; Barbosa, Marconi S.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
57.274365%
A recent paper \cite{CaeCaeSchBar06} proposed a provably optimal, polynomial time method for performing near-isometric point pattern matching by means of exact probabilistic inference in a chordal graphical model. Their fundamental result is that the chordal graph in question is shown to be globally rigid, implying that exact inference provides the same matching solution as exact inference in a complete graphical model. This implies that the algorithm is optimal when there is no noise in the point patterns. In this paper, we present a new graph which is also globally rigid but has an advantage over the graph proposed in \cite{CaeCaeSchBar06}: its maximal clique size is smaller, rendering inference significantly more efficient. However, our graph is not chordal and thus standard Junction Tree algorithms cannot be directly applied. Nevertheless, we show that loopy belief propagation in such a graph converges to the optimal solution. This allows us to retain the optimality guarantee in the noiseless case, while substantially reducing both memory requirements and processing time. Our experimental results show that the accuracy of the proposed solution is indistinguishable from that of \cite{CaeCaeSchBar06} when there is noise in the point patterns.; Comment: 9 pages...

Non-Linear Pattern-Matching against Unfree Data Types with Lexical Scoping

Egi, Satoshi
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
47.872305%
This paper proposes a pattern-matching system that enables non-linear pattern-matching against unfree data types. The system allows multiple occurrences of the same variables in a pattern, multiple results of pattern-matching and modularization of the way of pattern-matching for each data type at the same time. It enables us to represent pattern-matching against not only algebraic data types but also unfree data types such as sets, graphs and any other data types whose data have no canonical form and multiple ways of decomposition. I have realized that with a rule that pattern-matching is executed from the left side of a pattern and a rule that a binding to a variable in a pattern can be referred to in its right side of the pattern. Furthermore, I have realized modularization of these patterns with lexical scoping. In my system, a pattern is not a first class object, but a pattern-function that obtains only patterns and returns a pattern is a first class object. This restriction simplifies the non-linear pattern-matching system with lexical scoping. I have already implemented the pattern-matching system in the Egison programming language.; Comment: 25 pages, 3 figures

One-Dimensional Vector based Pattern Matching

Fouda, Y. M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/09/2014 Português
Relevância na Pesquisa
57.274365%
Template matching is a basic method in image analysis to extract useful information from images. In this paper, we suggest a new method for pattern matching. Our method transform the template image from two dimensional image into one dimensional vector. Also all sub-windows (same size of template) in the reference image will transform into one dimensional vectors. The three similarity measures SAD, SSD, and Euclidean are used to compute the likeness between template and all sub-windows in the reference image to find the best match. The experimental results show the superior performance of the proposed method over the conventional methods on various template of different sizes.

Flow analysis based on role and pattern matching

Wagh, Pooja
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
57.274365%
Flow analysis has always been a great concern for a network system. An attacker can gain important information through several ways by monitoring the frequency and timing of network packets or by impersonating another user through remote access. Access to a network system based on single-factor authentication is nothing but monitoring the perimeter around the network leaving a company's a network wide open for the inside threat. There is a necessity to develop a classic network to reduce or eliminate threats within the organization. This thesis will analyze the flows to inspect every activity performed within the network in order for the untrusted flows to earn their way in becoming trusted flows based on notion of flow activity matching a specified pattern affiliated with the role.

Palm-Print Pattern Matching Based on Features Using Rabin-Karp for Person Identification

Kanchana, S.; Balakrishnan, G.
Fonte: Hindawi Publishing Corporation Publicador: Hindawi Publishing Corporation
Tipo: Text
Português
Relevância na Pesquisa
47.70996%
Palm-print based individual identification is regarded as an effectual method for identifying persons with high confidence. Palm-print with larger inner surface of hand contains many features such as principle lines, ridges, minutiae points, singular points, and textures. Feature based pattern matching has faced the challenge that the spatial positional variations occur between the training and test samples. To perform effective palm-print features matching, Rabin-Karp Palm-Print Pattern Matching (RPPM) method is proposed in this paper. With the objective of improving the accuracy of pattern matching, double hashing is employed in RPPM method. Multiple patterns of features are matched using the Aho-Corasick Multiple Feature matching procedure by locating the position of the features with finite set of bit values as an input text, improving the cumulative accuracy on hashing. Finally, a time efficient bit parallel ordering presents an efficient variation on matching the palm-print features of test and training samples with minimal time. Experiment is conducted on the factors such as pattern matching efficiency rate, time taken on multiple palm-print feature matching efficiency, and cumulative accuracy on hashing.