105 research outputs found
Grammatica: an implementation of algebraic graph transformation on Mathematica
No full textGrammatica is a prototype implementation of algebraic graph transformation based on relation algebra. It has been
implemented using Mathematica on top of the Combinatorica package, and runs therefore on most platforms. It consists of
Mathematica routines for representing, manipulating, displaying and transforming graphs, as well as routines implementing
some relation algebra-theoretic operations on graphs. It supports both interactive and automatic application of double-pushout
graph productions, being therefore both a teaching aid and a research tool for algebraic graph transformation
The landscape of virus-host protein–protein interaction databases
No full textKnowledge of virus-host interactomes has advanced exponentially in the last decade by the use of high-throughput screening technologies to obtain a more comprehensive landscape of virus-host protein–protein interactions. In this article, we present a systematic review of the available virus-host protein–protein interaction database resources. The resources covered in this review are both generic virus-host protein–protein interaction databases and databases of protein–protein interactions for a specific virus or for those viruses that infect a particular host. The databases are reviewed on the basis of the specificity for a particular virus or host, the number of virus-host protein–protein interactions included, and the functionality in terms of browse, search, visualization, and download. Further, we also analyze the overlap of the databases, that is, the number of virus-host protein–protein interactions shared by the various databases, as well as the structure of the virus-host protein–protein interaction network, across viruses and hosts.This research was partially supported by the Spanish Ministry of Science and Innovation, and the European Regional Development Fund, through project PID2021-126114NB-C44 (FEDER/MICINN/AEI).Peer ReviewedPostprint (published version
On the maximum common embedded subtree problem for ordered trees
No full textThe maximum common embedded subtree problem, which generalizes the
subtree homeomorphism problem, is reduced for ordered trees to a variant
of the longest common subsequence problem, called the longest common
balanced sequence problem. While the maximum common embedded subtree
problem is known to be APX-hard for unordered trees, an exact solution
for ordered trees can be found in polynomial time. A dynamic programming
algorithm is presented that solves the longest common balanced sequence
problem, and thus the maximum common embedded subtree problem, in
(m^2n^2)$ time, where m and n are the number of edges in the
trees.Postprint (published version
Composición de textos científicos con LATEX
No full textEl LaTeX es uno de los sistemas de tratamiento de textos científicos de más amplia difusión dentro del mundo académico. Se caracteriza por la gran calidad del trabajo impreso, calidad que puede competir con la de los trabajos impresos por las principales editoriales científicas del mundo. Este libro pretende dar a conocer el sistema LaTeX en el contexto de la composición de textos científicos. Así, puede servir de introducción a aquellos estudiantes que se inicien en la escritura científica y, a la vez, puede resultar un texto de consulta permanente para profesores e investigadores
Tree edit distance and common subtrees
No full textThe relationship between tree edit distance and maximum common
subtrees is established, showing that a tree edit distance constrained
by insertion and deletions on leaves only and by a simple condition on
the cost of the tree edit operations, corresponds to a maximum commonsubtree isomorphism, allowing thus the use of known tree edit distance algorithms to solve the maximum common subtree problem, and viceversa. Further, a tree distance based on the size of a maximum common subtree is introduced.Postprint (published version
On the maximum common embedded subtree problem for ordered trees
No full textThe maximum common embedded subtree problem, which generalizes the
subtree homeomorphism problem, is reduced for ordered trees to a variant
of the longest common subsequence problem, called the longest common
balanced sequence problem. While the maximum common embedded subtree
problem is known to be APX-hard for unordered trees, an exact solution
for ordered trees can be found in polynomial time. A dynamic programming
algorithm is presented that solves the longest common balanced sequence
problem, and thus the maximum common embedded subtree problem, in
(m^2n^2)$ time, where m and n are the number of edges in the
trees
On the maximum common embedded subtree problem for ordered trees
No full textThe maximum common embedded subtree problem, which generalizes the
subtree homeomorphism problem, is reduced for ordered trees to a variant
of the longest common subsequence problem, called the longest common
balanced sequence problem. While the maximum common embedded subtree
problem is known to be APX-hard for unordered trees, an exact solution
for ordered trees can be found in polynomial time. A dynamic programming
algorithm is presented that solves the longest common balanced sequence
problem, and thus the maximum common embedded subtree problem, in
(m^2n^2)$ time, where m and n are the number of edges in the
trees.Postprint (published version
An Efficient representation for sparse graphs
No full textThe design of efficient graph algorithms usually precludes the test of
edge existence, because an efficient support of that operation already
requires time (n^2) for the initialization of an
adjacency-matrix representation. We describe an alternative
representation of static directed graphs taking (n+m)
initialization time and using (n^2) space, which supports the
efficient implementation of all usual operations on static graphs. The
sparse graph representation allows the design of efficient graph
algorithms using both iteration over all vertices adjacent with a
given vertex and edge-existence operations, although at the expense of
additional (uninitialized) space which may, nevertheless, be used for
other purposes. To the best of our knowledge, the representation leads
to the first graph algorithms with the disconcerting property that the
time complexity is better than the space complexity.Postprint (published version
Simple and efficient tree comparison
No full textA new distance metric for rooted trees is presented which is based on
the largest common forest of two rooted trees. The new measure is
superior to previous measures based on tree edit distance, because no
particular tree edit operations together with their costs or weights
need to be defined. The
metric can be computed in expected time linear in the number of nodes,
on rooted trees of unbounded degree, either unordered or ordered,
labeled or unlabeled. An algorithm for computing the metric is given
which is based on a simple and efficient bottom-up algorithm for finding
all common rooted subtrees in a forest.Postprint (published version
An Efficient representation for sparse graphs
No full textThe design of efficient graph algorithms usually precludes the test of
edge existence, because an efficient support of that operation already
requires time (n^2) for the initialization of an
adjacency-matrix representation. We describe an alternative
representation of static directed graphs taking (n+m)
initialization time and using (n^2) space, which supports the
efficient implementation of all usual operations on static graphs. The
sparse graph representation allows the design of efficient graph
algorithms using both iteration over all vertices adjacent with a
given vertex and edge-existence operations, although at the expense of
additional (uninitialized) space which may, nevertheless, be used for
other purposes. To the best of our knowledge, the representation leads
to the first graph algorithms with the disconcerting property that the
time complexity is better than the space complexity.Postprint (published version
- …
