5.343. sequence_folding

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

J.Β Pearson

Constraint

πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšπš˜πš•πšπš’πš—πš(π™»π™΄πšƒπšƒπ™΄πšπš‚)

Argument
π™»π™΄πšƒπšƒπ™΄πšπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πš—πšŽπš‘πš-πšπšŸπšŠπš›)
Restrictions
|π™»π™΄πšƒπšƒπ™΄πšπš‚|β‰₯1
πš›πšŽπššπšžπš’πš›πšŽπš(π™»π™΄πšƒπšƒπ™΄πšπš‚,[πš’πš—πšπšŽπš‘,πš—πšŽπš‘πš])
π™»π™΄πšƒπšƒπ™΄πšπš‚.πš’πš—πšπšŽπš‘β‰₯1
π™»π™΄πšƒπšƒπ™΄πšπš‚.πš’πš—πšπšŽπš‘β‰€|π™»π™΄πšƒπšƒπ™΄πšπš‚|
πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_𝚜𝚎𝚚(π™»π™΄πšƒπšƒπ™΄πšπš‚,πš’πš—πšπšŽπš‘)
π™»π™΄πšƒπšƒπ™΄πšπš‚.πš—πšŽπš‘πšβ‰₯1
π™»π™΄πšƒπšƒπ™΄πšπš‚.πš—πšŽπš‘πšβ‰€|π™»π™΄πšƒπšƒπ™΄πšπš‚|
Purpose

Express the fact that a sequence is folded in a way that no crossing occurs. A sequence is modelled by a collection of letters. For each letter l 1 of a sequence, we indicate the next letter l 2 located after l 1 that is directly in contact with l 1 (l 1 itself if such a letter does not exist).

Example
πš’πš—πšπšŽπš‘-1πš—πšŽπš‘πš-1,πš’πš—πšπšŽπš‘-2πš—πšŽπš‘πš-8,πš’πš—πšπšŽπš‘-3πš—πšŽπš‘πš-3,πš’πš—πšπšŽπš‘-4πš—πšŽπš‘πš-5,πš’πš—πšπšŽπš‘-5πš—πšŽπš‘πš-5,πš’πš—πšπšŽπš‘-6πš—πšŽπš‘πš-7,πš’πš—πšπšŽπš‘-7πš—πšŽπš‘πš-7,πš’πš—πšπšŽπš‘-8πš—πšŽπš‘πš-8,πš’πš—πšπšŽπš‘-9πš—πšŽπš‘πš-9

FigureΒ 5.343.1 gives the folded sequence associated with the previous example. Each number represents the index of an item. The πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšπš˜πš•πšπš’πš—πš constraint holds since no crossing occurs.

Figure 5.343.1. Folded sequence (in blue) of the Example slot: links from a letter to a distinct letter are represented by a dashed arc, while self-loops are not drawn
ctrs/sequence_folding-1-tikz
Typical
|π™»π™΄πšƒπšƒπ™΄πšπš‚|>2
πš›πšŠπš—πšπšŽ(π™»π™΄πšƒπšƒπ™΄πšπš‚.πš—πšŽπš‘πš)>1
Usage

Motivated by RNA foldingΒ [FlammHofackerStadler99].

See also

implies (items to collection): πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš•πšŽπš‘_πšŒπš‘πšŠπš’πš—_πš•πšŽπšœπšœ.

Keywords

application area: bioinformatics.

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

combinatorial object: sequence.

constraint type: decomposition.

geometry: geometrical constraint.

Arc input(s)

π™»π™΄πšƒπšƒπ™΄πšπš‚

Arc generator
π‘†πΈπΏπΉβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš•πšŽπšπšπšŽπš›πšœ)

Arc arity
Arc constraint(s)
πš•πšŽπšπšπšŽπš›πšœ.πš—πšŽπš‘πšβ‰₯πš•πšŽπšπšπšŽπš›πšœ.πš’πš—πšπšŽπš‘
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™»π™΄πšƒπšƒπ™΄πšπš‚|

Arc input(s)

π™»π™΄πšƒπšƒπ™΄πšπš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš•πšŽπšπšπšŽπš›πšœ1,πš•πšŽπšπšπšŽπš›πšœ2)

Arc arity
Arc constraint(s)
β‹πš•πšŽπšπšπšŽπš›πšœ2.πš’πš—πšπšŽπš‘β‰₯πš•πšŽπšπšπšŽπš›πšœ1.πš—πšŽπš‘πš,πš•πšŽπšπšπšŽπš›πšœ2.πš—πšŽπš‘πšβ‰€πš•πšŽπšπšπšŽπš›πšœ1.πš—πšŽπš‘πš
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™»π™΄πšƒπšƒπ™΄πšπš‚|*(|π™»π™΄πšƒπšƒπ™΄πšπš‚|-1)/2

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.343.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.343.2. Initial and final graph of the πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšπš˜πš•πšπš’πš—πš constraint
ctrs/sequence_foldingActrs/sequence_foldingB
(a) (b)
Signature

Consider the first graph constraint. Since we use the 𝑆𝐸𝐿𝐹 arc generator on the π™»π™΄πšƒπšƒπ™΄πšπš‚ collection the maximum number of arcs of the final graph is equal to |π™»π™΄πšƒπšƒπ™΄πšπš‚|. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™»π™΄πšƒπšƒπ™΄πšπš‚| to 𝐍𝐀𝐑𝐂β‰₯|π™»π™΄πšƒπšƒπ™΄πšπš‚| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Consider now the second graph constraint. Since we use the πΆπΏπΌπ‘„π‘ˆπΈ(<) arc generator on the π™»π™΄πšƒπšƒπ™΄πšπš‚ collection the maximum number of arcs of the final graph is equal to |π™»π™΄πšƒπšƒπ™΄πšπš‚|Β·(|π™»π™΄πšƒπšƒπ™΄πšπš‚|-1)/2. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™»π™΄πšƒπšƒπ™΄πšπš‚|Β·(|π™»π™΄πšƒπšƒπ™΄πšπš‚|-1)/2 to 𝐍𝐀𝐑𝐂β‰₯|π™»π™΄πšƒπšƒπ™΄πšπš‚|Β·(|π™»π™΄πšƒπšƒπ™΄πšπš‚|-1)/2 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.343.3 depicts the automaton associated with the πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšπš˜πš•πšπš’πš—πš constraint. Consider the i th and the j th (i<j) items of the collection π™»π™΄πšƒπšƒπ™΄πšπš‚. Let π™Έπ™½π™³π™΄πš‡ i and π™½π™΄πš‡πšƒ i respectively denote the πš’πš—πšπšŽπš‘ and the πš—πšŽπš‘πš attributes of the i th item of the collection π™»π™΄πšƒπšƒπ™΄πšπš‚. Similarly, let π™Έπ™½π™³π™΄πš‡ j and π™½π™΄πš‡πšƒ j respectively denote the πš’πš—πšπšŽπš‘ and the πš—πšŽπš‘πš attributes of the j th item of the collection π™»π™΄πšƒπšƒπ™΄πšπš‚. To each quadruple (π™Έπ™½π™³π™΄πš‡ i ,π™½π™΄πš‡πšƒ i ,π™Έπ™½π™³π™΄πš‡ j ,π™½π™΄πš‡πšƒ j ) corresponds a signature variable S i,j , which takes its value in {0,1,2}, as well as the following signature constraint:

(π™Έπ™½π™³π™΄πš‡ i β‰€π™½π™΄πš‡πšƒ i )∧(π™Έπ™½π™³π™΄πš‡ j β‰€π™½π™΄πš‡πšƒ j )∧(π™½π™΄πš‡πšƒ i β‰€π™½π™΄πš‡πšƒ j )⇔S i,j =0 ∧

(π™Έπ™½π™³π™΄πš‡ i β‰€π™½π™΄πš‡πšƒ i )∧(π™Έπ™½π™³π™΄πš‡ j β‰€π™½π™΄πš‡πšƒ j )∧(π™½π™΄πš‡πšƒ i >π™Έπ™½π™³π™΄πš‡ j )∧(π™½π™΄πš‡πšƒ j β‰€π™½π™΄πš‡πšƒ i )⇔S i,j =1.

Figure 5.343.3. Automaton of the πšœπšŽπššπšžπšŽπš—πšŒπšŽ_πšπš˜πš•πšπš’πš—πš constraint
ctrs/sequence_folding-2-tikz