Jeux Técleux Octobre 2009
Gerard Sookahet
Pour ce jeu, je vous propose quelque chose de différent.
Il existe un concours national d'informatique du nom de Prologin:
Je propose donc de répondre aux 4 problèmes du questionnaire
de sélection de la page 3:
http://www.prologin.org/files/prologin2010/Prologin_QCM2010.pdf
Bon téclage :-)
GS
--------
Dans tous les exercices proposés, une séquence d'ADN sera une
suite finie constituée de lettres dans l'ensemble {A, T, G, C}.
Chaque élément de la séquence d'ADN sera appelé un nucléotide.
P1. Nucléotide
On vous donne en entrée une séquence d'ADN de longueur n.
Écrivez une fonction qui renvoie le nucléotide (la lettre)
le plus présent. Si c'est le cas de plusieurs, renvoyez
celle qui vient en premier dans l'ordre alphabétique.
Exemple :
Séquence d’ADN : ATTGCCATATCC
Réponse : C
P2. Les acides aminés
Lors de la transcription (simplifiée !) d’une séquence d’ADN
en suite d’acides aminés, chaque groupement de trois nucléotides
de la séquence d’ADN est transformé en acide aminé.
Écrivez une fonction qui, étant donné une séquence d’ADN de
longueur n et la table de transcription, renvoie la suite
d’acides aminés correspondante. On assure que tout le brin
d’ADN pourra être transcrit, et que n est multiple de 3.
Exemple :
Séquence d’ADN : ATTGCCTCC
Table de transcription : ATT -> isoleucine ; TCC -> serine ;
GCC -> alanine
Réponse : isoleucine alanine serine
P3. Sous-séquences
On cherche à analyser les fréquences d’apparition des
sous-séquences d’une séquence d’ADN donnée en entrée.
Écrivez une fonction qui renvoie la sous-séquence contiguë
de longueur L de la chaîne d’ADN la plus fréquente.
Dans le cas où plusieurs sous-séquences apparaissent un même
nombre de fois, affichez celle qui vient en premier dans
l’ordre alphabétique.
Exemple :
Séquence d’ADN : AATTCGGCCGATCGTCGAATTCGATA
L = 4
Réponse : AATT
P4. Mutations (Question bonus)
On vous donne en entrée deux séquences ADN de tailles n1 et n2.
On souhaite calculer le nombre minimal de transformations pour
passer de la première séquence à la deuxième. Les transformations
possibles sont la modification, l'ajout ou la suppression d'un
nucléotide. Les deux séquences sont très similaires ; on garantit
donc que l'on puisse passer de l'une à l'autre en moins de
100 transformations.
Écrivez une fonction renvoyant le résultat demandé.
Exemple :
Première séquence : ATTGCAAA
Seconde séquence : ATCTAAAT
Réponse : 4
Aric
package require Tcl 8.6 ;# a cause de [lsort -stride]
proc nucleotide {sequence} {
foreach nucleotide [split $sequence ""] {
incr ct($nucleotide)
}
return [lindex [lsort -stride 2 -index 1 -integer -decreasing \
[lsort -stride 2 [array get ct]]] 0]
}
proc acides_amines {sequence table_de_transcription} {
# je presume que la table ait un format comme ceci :
# " PATRON -> NOM ; PATRON -> NOM ; ... "
# et que la presence des espaces ne soit pas garantie
set map [list]
foreach sous_table [split $table_de_transcription ";"] {
if {[string trim $sous_table] eq ""} {
break
}
regexp {(\w{3})\s*\-\>\s*(\w+)} $sous_table match patron nom
lappend map $patron $nom
}
foreach acide [regexp -all -inline {.{3}} $sequence] {
lappend reponse [string map $map $acide]
}
return $reponse
}
proc sous-sequences {sequence L} {
for {set i 0; set j [expr {$L - 1}]} \
{$j < [string length $sequence]} {incr i; incr j} {
incr ct([string range $sequence $i $j])
}
return [lindex [lsort -stride 2 -index 1 -integer -decreasing \
[lsort -stride 2 [array get ct]]] 0]
}
proc mutations {sequence1 sequence2} {
# La solution consiste a calculer le distance de Levenshtein.
# Cette procedure a fait son debut sur le wiki international :
# http://wiki.tcl.tk/3070
# La procedure est basee sur l'algorithme sur Wikipedia :
# http://fr.wikipedia.org/wiki/Distance_de_Levenshtein
# j'aurais du adapter le code au probleme, mais comme je suis
paresseux...
set s $sequence1
set t $sequence2
# special case: $s is an empty string
if {$s eq ""} {
return [string length $t]
}
# initialize first row in table
for {set i 0} {$i <= [string length $t]} {incr i} {
lappend prevrow $i
}
set i 0
foreach schar [split $s ""] {
incr i
set j 0
set row [list $i]
foreach tchar [split $t ""] {
incr j
set cost [expr {$schar ne $tchar}] ;# $cost is 0 if same, 1 if
different
# difference between $schar and $tchar is minimum of:
# [lindex $prevrow $j] + 1 = cost of deletion
# [lindex $row $j-1] + 1 = cost of insertion
# [lindex $prevrow $j-1] + $cost = cost of substitution
# (zero if same char)
lappend row [expr {min([lindex $prevrow $j] + 1,
[lindex $row [expr {$j-1}]] + 1,
[lindex $prevrow [expr {$j-1}]] + $cost)}]
}
set prevrow $row
}
# Levenshtein distance is value at last cell of last row
return [lindex $row end]
}
Gerard Sookahet
Bonsoir,
Une autre solution pour le Problème 1 avec Tcl 8.5:
proc nucleotide {sequence} {
foreach nucleotide [split $sequence ""] {
if ![info exists compte($nucleotide)] {
set compte($nucleotide) 1
} else {incr compte($nucleotide)}
}
set n 0
foreach nucleotide [array names compte] {
# puts "$nucleotide -> $compte($nucleotide)"
if {$compte($nucleotide) > $n} then {
set n $compte($nucleotide)
set L $nucleotide
}
}
return $L
}
GS