Detail of EuGène's directed acyclic graph and algorithm. The zoomed region contains the two first nucleotides of the example sequence of Figure 3 (C at position
i - 1, and A at position
i), and two annotation tracks (UTR5' for
j and exon in frame 2 for
j + 1). The contents edges
c connect the
l vertices to the following
r vertices of the same track. Transition edges
t are either horizontal and link the
r vertices to the
l vertices of the same track, or transversal and link the
r vertices to all possible
l vertices according to the occurrence of a biological signal in the sequence. In this example, between

and

a vertex

allows the transition from the UTR5' track at position
i - 1 to the exonic track at
i because the A nucleotide at position
i is the first nucleotide of a potential start codon ATG. The dynamic programming algorithm used in EuGÈNE determines, for each vertex
r, which vertex precedes
r in the optimal path. In this example, at position
i for the track
j the best path leading to

from the left has a weight

(only one origin is possible). For the track
j + 1, the best path leading to

will be attributed a weight of either

, whatever the lower.