Information Technology Reference
In-Depth Information
1.8
Graphs and Interactions
A molecule is built over a multiset of atoms, but this multiset does not provide all
the information about the relations holding among its atoms. In chemistry, the mul-
tiset of a molecule is also called
molecular formula, while the
structural formula
is
a graph, that is a set of
nodes
connected by
edges
or
arcs
(usually drawn by lines
or curves, oriented or not, and possibly tagged with specific data). Two molecules
having the same molecular formula, but different structural formulae are called
isomers
.
A graph is the mathematical abstraction of point-line (or point-arrow) diagrams.
In any context where some entities are related, possibly in many different ways,
graphs naturally emerge. Mathematically speaking, a
graph
is a set of “arrows”
(edges, arcs), each of which connects two nodes (tags, or marks may be associated
to nodes and/or arrows). The terminology of graphs is very intuitive and all the
important features of a graph, such as
path, cycle, degree, component
can be mathe-
matically expressed by using the basic notions of set, sequence, multiset, operation,
and relation. For example, a
path
is a sequence of nodes, where consecutive nodes
are connected by an edge. A graph is
connected
if any two nodes are connected by
some path. A
cycle
is a path where the first node coincides with the last one. A graph
is
acyclic
if it does not have cycles. The graphs which are connected and without
cycles are also called
unrooted trees
.
From an unrooted tree, a rooted tree can be univocally obtained by choosing one
node as root. Connection and absence of cycles ensure this possibility. In fact, any
node has to be connected to some other node. Therefore, from the chosen root we get
its sons and, iteratively, from them we get other nodes until we reach some leaves.
No node can be reached twice, because the graph is assumed without cycles.
1.8.1
Graphs of Molecule Structures
Molecules are graphs where nodes are atoms (or atom aggregates) and edges are the
chemical bonds among atoms (some tags can be added to nodes and/or edges for
expressing specific properties of chemical interest, such as the types or strengths of
bonds). For example, a basic components of RNA and DNA molecules are
pentoses
,
sugar molecules constituted by carbons and water molecules.
Ribose
C
5
H
10
O
5
is a
pentose which includes five carbons and five molecules of water (
H
2
O
). The posi-
tions of the five carbons in pentoses are identified by primed numbers.
Deoxyribose
C
5
H
10
O
4
derives from ribose by removing an Oxygen in position 2
.
Figure 1.10 represents the graph of the structural formula of a
nucleotide
,the
basic component of DNA polymers. It is constituted by three parts:
1.
deoxyribose
,
2.
nitrogenous base
(
adenine
in Fig. 1.10),
3.
phosphate group
PO
4
.
