Information Technology Reference
In-Depth Information
The linear/circular language accepted by a finite automaton
A
is defined as
L(
A
)
L(
A
)
•
, where
L(
A
)
is the linear language accepted by the automaton
A
defined in the usual way.
∪
DEFINITION 6 A linear/circular language
L
⊆ Σ
∗
∪ Σ
•
is called
regular
if
there exists a finite automaton
A
that accepts the linear and circular parts of
L
(i.e., that accepts
L
∩ Σ
∗
and
L
∩ Σ
•
).
We can now formulate the main result presented in this section.
THEOREM 2 Let
J
⊆ Σ
∗
be a set of plugs and let
A
⊆ Σ
∗
∪ Σ
•
be a finite
axiom set. Then the set
X
defined as in theorem 1 equals the linear/circular
language accepted by a finite automaton
A
and is therefore regular.
Theorem 2 shows that the rewriting systems based on context-free recom-
binations are computationally weak, having only the power of finite automata.
This is one more indicator that, most probably, the presence of pointers alone
does not provide all the information needed for accurate splicing during gene
rearrangement.
GUIDED RECOMBINATION SYSTEMS
As seen previously, the estimated running time of a pointer-search-and-match
algorithm simulating gene rearrangement is prohibitively high. The previous
section showed that the computational power of a formal computational model
based on such context-free recombinations is very low—namely, that of finite
automata. These and other biological arguments point to the fact that this model
should be further refined to accurately reflect the biological reality [17]. We
have introduced the additional assumption that homologous recombination is
influenced by the presence of certain
guiding contexts
flanking the pointers
present at the MDS-IES junctions [9]. The observed dependence on the old
macronuclear sequence for correct IES removal in the distantly related ciliate
Paramecium
suggests that this is the case [11]. This restriction captures the
fact that the pointers do not contain all the information for accurate splicing
during gene unscrambling. In particular, we defined the notion of a
guided
recombination system
based on operation 2 and proved that such systems have
the computational power of a TM, the most widely used theoretical model of
electronic computers [9].
We defined the contexts that restrict the use of recombinations by a
splicing
scheme
[3, 4, 9] a pair
(
, the pairing
relation of the scheme, is a binary relation between triplets of nonempty words
satisfying the following condition: if
(p,x,q)
∼
(p
,y,q
)
, then
x
=
y
.
In the splicing scheme
(
Σ
,
∼
)
, pairs
(p,x,q)
∼
(p
,x,q
)
now define the
contexts necessary for a recombination between pointers
x
. Then we define
contextual intramolecular recombination
as
Σ
,
∼
)
where
Σ
is the alphabet and
∼
