Regulation of Gene Expression

Regulation of Gene Expression

• Gene expression transforms gene information into functional products like proteins or RNA.
• It is regulated for adaptation and to prevent overproduction.

Transcriptional Control

• Takes place when DNA is transcribed into RNA.

Positive Regulation

• Activator proteins bind to DNA to enhance transcription.
• The lac operon in E. coli functions as an example.

Negative Regulation

• Repressor proteins bind to DNA to diminish transcription.
• The trp operon in E. coli functions as an example.

Post-transcriptional Control

• Occurs after DNA transcription into RNA.

RNA Splicing

• Splicing removes introns from pre-mRNA and joins exons.
• Alternative splicing creates diverse mRNA molecules from one pre-mRNA.

RNA Stability

• mRNA stability influences protein production.
• miRNAs can bind to mRNA, triggering degradation.

Translation

• Translation is regulated by initiation factors and repressor proteins.
• Ferritin mRNA translation depends on iron levels.

Post-translational Control

• Happens post-protein synthesis.

Protein Folding

• Functional proteins require proper folding.
• Chaperone proteins aid in correct folding.

Protein Modification

• Proteins undergo modification with chemical groups.
• Phosphorylation can activate or deactivate proteins.

Protein Degradation

• Proteases can degrade proteins.
• Ubiquitination marks proteins for degradation.

Eukaryotic vs. Prokaryotic Gene Expression

• Transcription factors bind to DNA, influencing transcription.
• Control can be exerted over RNA splicing, stability, and translation.
• Post-synthesis, proteins must fold correctly and can be modified.
• Eukaryotic gene expression exceeds prokaryotic in complexity.

Algorithmes gloutons

• A simple approach to solving optimization problems.
• They make the best choice at each step without considering future consequences.
  • Easy to implement and often very efficient.
  • Do not always guarantee the optimal solution.

Principe general

1. Identify a greedy choice criterion.
2. Apply this criterion iteratively to construct a solution.
3. Check if the solution obtained is optimal (or acceptable).

Exemples classiques

Problème du rendu de monnaie

• Given a set of coins and an amount to be returned, minimize the number of coins used.
• Algorithme glouton:*

1. Sort coins in descending order of value.
2. Add as many coins of the largest value as possible without exceeding the remaining amount.
3. Repeat step 2 with the next lower value coin.

• Exemple:* Return €4.67 with coins of {€2, €1, €0.50, €0.20, €0.05, €0.02, €0.01}.

• 2 coins of €2 → remains €0.67

• 1 coin of €0.50 → remains €0.17

• 0 coin of €0.20 → remains €0.17

• 3 coins of €0.05 → remains €0.02

• 1 coin of €0.02 → remains €0

• Optimal for "canonical" coin systems (e.g., euro or US dollar).

Problème du sac à dos fractionnaire

• Given a set of objects with a value and a weight, and a knapsack with a maximum capacity, maximize the total value of the objects placed in the knapsack. A fraction of an object can be taken.
• Algorithme glouton*

1. Calculate the value/weight ratio for each object.
2. Sort the objects in descending order of this ratio.
3. Add the objects to the knapsack starting with the one with the highest ratio, until the bag is full.

• Exemple*

Knapsack capacity: 50

1. Add A (10, 60) → remains 40
2. Add B (20, 100) → remains 20
3. Add 2/3 of C (20, 80)

Total value: $60 + 100 + 80 = 240$

• The algorithm is optimal for the fractional knapsack problem.

Quand utiliser un algorithme glouton ?

• The problem has an optimization structure.
• It can be proved that the greedy choice at each step leads to an optimal solution.
• In the absence of proof of optimality, a sub-optimal solution can be accepted.

Limites

• Not all problems can be solved optimally with a greedy algorithm.
• It is important to choose the greedy choice criterion well.
• In some cases, it may be necessary to explore several avenues to find an acceptable solution.

Conclusion

• Greedy algorithms are a powerful tool for solving optimization problems, but it is important to know their limitations and use them with discernment.

Algorithmes de tri

Tri par sélection

Principe

1. Search for the smallest element in the array
2. Exchange with the element of index 0
3. Search for the smallest element of the array starting from index 1
4. Exchange with the element of index 1 5....

Exemple

5 1 4 2 8
1 5 4 2 8
1 2 4 5 8
1 2 4 5 8
1 2 4 5 8

Pseudo-code

procedure tri_selection(tableau T, entier n)
  pour i allant de 0 à n - 2 faire
    minIndex = i
    pour j allant de i + 1 à n - 1 faire
      si T[j] < T[minIndex] alors
        minIndex = j
      fin si
    fin pour
    si minIndex != i alors
      echanger T[i] et T[minIndex]
    fin si
  fin pour
end procedure

Complexité

• $O(n^2)$ regardless of the array.

Tri par insertion

Principe

• Browse the array and insert each element in its place among the previous elements already sorted.

Exemple

5 1 4 2 8
1 5 4 2 8
1 4 5 2 8
1 2 4 5 8
1 2 4 5 8

Pseudo-code

procedure tri_insertion(tableau T, entier n)
  pour i allant de 1 à n - 1 faire
    cle = T[i]
    j = i - 1
    tant que j >= 0 et T[j] > cle faire
      T[j + 1] = T[j]
      j = j - 1
    fin tant que
    T[j + 1] = cle
  fin pour
end procedure

Complexité

• $O(n^2)$ in the worst case (array sorted in reverse order).
• $O(n)$ in the best case (array already sorted).

Tri à bulles

Principe

• Compare adjacent elements and swap them if they are poorly ordered.
• Repeat the operation until there are no more swaps.

Exemple

5 1 4 2 8
1 5 4 2 8
1 4 5 2 8
1 4 2 5 8
1 4 2 5 8

Pseudo-code

procedure tri_bulles(tableau T, entier n)
  repeter
    echange = faux
    pour i allant de 0 à n - 2 faire
      si T[i] > T[i + 1] alors
        echanger T[i] et T[i + 1]
        echange = vrai
      fin si
    fin pour
  jusqu'a echange = faux
end procedure

Complexité

• $O(n^2)$ in the worst case (array sorted in reverse order).
• $O(n)$ in the best case (array already sorted).