1,721,004 research outputs found
A Review on Models and Algorithms for Motif Discovery in Protein-Protein InteractionNetwork
No full textSeveral algorithms have been recently designed to identify motifs in biological networks, particularly in protein-protein interaction networks. Motifs correspond to repeated modules in the network that may be of biological interest. The approaches proposed in the literature often differ in the definition of a motif, the way the occurrences of a motif are counted and the way their statistical significance is assessed. This has strong implications on the computational complexity of the discovery process and on the type of results that can be expected. This review presents in a systematic way the different computational settings outlining their main features and limitations
Line-based object recognition using Hausdorff distance: from range images to molecular secondary structures
No full textObject recognition algorithms are fundamental tools in automatic
matching of geometric shapes within a background scene. Many approaches
have been proposed in the past to solve the object recognition
problem. Two of the key aspects that distinguish them in terms of
their practical usability are: (i) the type of input model description
and (ii) the comparison criteria used.
In this paper we introduce a novel scheme for 3D object recognition
based on line segment representation of the input shapes and comparison
using the Hausdorff distance. This choice of model representation
provides the flexibility to apply the scheme in different application areas.
We define several variants of the Hausdorff distance to compare
the models within the framework of well defined metric spaces.
We present a matching algorithm that efficiently finds a pattern in
a 3D scene. The algorithm approximates a minimization procedure of
the Hausdorff distance. The output error due to the approximation is
guaranteed to be within a known constant bound.
Practical results are presented for two classes of objects: (i) polyhedral
shapes extracted from segmented range images and (ii) secondary
structures of large molecules. In both cases the use of our
approximate algorithm allows to match correctly the pattern in the
background while achieving the efficiency necessary for practical use
of the scheme. In particular the performance is improved substantially
with minor degradation of the quality of the matching
Proceedings of the First International Symposyum on 3D Data Processing Visualization and Transmission
No full textMining Over-Represented 3D Patterns of Secondary Structures in Proteins
No full textABSTRACT
We consider the problem of ̄nding over-represented arrange-
ments of Secondary Structure Elements (SSEs) in a given
dataset of representative protein structures. While most pa-
pers in the literature study the distribution of geometrical
properties, in particular angles and distances, between pairs
of interacting SSEs, in this paper we focus on the distribu-
tion of angles of all quartets of SSEs and on the extraction of
over-represented angular patterns. We propose a variant of
the Apriori method that obtains over-represented arrange-
ments of quartets of SSEs by combining arrangements of
triplets of SSEs. This speci ̄c case will pose the basis for
a natural extension of the problem to any given number of
SSEs. We analyze the results of our method on a dataset of
300 non redundant proteins
Binding Balls: Fast detection of Binding Sites using a property of Spherical Fourier Transform
No full textABSTRACT
The functional prediction of proteins is one of the most challenging problems in modern
biology. An established computational technique involves the identification of threedimensional
local similarities in proteins. In this article, we present a novel method to
quickly identify promising binding sites. Our aim is to efficiently detect putative binding
sites without explicitly aligning them. Using the theory of Spherical Harmonics, a candidate
binding site is modeled as a Binding Ball. The Binding Ball signature, offered by the
Spherical Fourier coefficients, can be efficiently used for a fast detection of putative regions.
Our contribution includes the Binding Ball modeling and the definition of a scoring function
that does not require aligning candidate regions. Our scoring function can be computed
efficiently using a property of Spherical Fourier transform (SFT) that avoids the evaluation
of all alignments. Experiments on different ligands show good discrimination power when
searching for known binding sites. Moreover, we prove that this method can save up to 40%
in time compared with traditional approaches
Effective Labeling of Molecular Surface Points to Matching Cavitiesand Locate Putative Binding Sites
No full textAlgorithmic Re-Structuring and Data Replication for Protein Structure Comparison on a Grid
No full textThis paper describes a major restructuring of PROuST, a method for protein structure comparison, for an efficient porting to the Grid. PROuST consists of different components: an index-based search that produces a list of proteins that are good candidates for similarity, and a dynamic programming algorithm that aligns the target protein with each candidate protein. Both components use the same geometric properties of secondary structure elements of proteins. Thus, an important issue arises when porting the application to the Grid, i.e. the tradeoff between data transfer and data recomputation. Our restructured application avoids recomputation by re-using the data as much as possible, once they are accessed. The algorithmic changes to PROuST allow to reduce the number of data accesses to storage elements and consequently the execution time. This paper also discusses data replication policies on a Grid environment to optimize the data transfer time
- …
