Discussion :

[lilly74]

Bonjour,
je débute en python et je dois créer un script déterminant les meilleurs alignements possibles entre deux séquences.
J'ai créé une matrice de coût selon une distance donnée: je la remplis en partant du coin supérieur gauche en allant vers le coin inférieur droit.
Jusqu'à ce point, pas de problème
Pour la suite, il faut que je "remonte" en partant du coin inférieur droit jusqu'au supérieur gauche en affichant les meilleurs alignements:
si je suis en (i,j) je regarde en (i-1,j) (i, j-1) et (i-1, j-1) et je prends les plus petits que je stocke dans une (des) liste(s).
Je veux créer une liste contenant toutes les listes qui vont se créer et se modifier à chaque tour:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from Matrice_Cout import *
from Levenshtein import *
from copy import *
 
compteur = 0
 
 
def Alignement(x, y, i, j, T, L):
    """Prend en entrée les deux séquences à aligner,
    la matrice des couts,
    et la position actuelle dans la matrice des couts
    (ligne i, colonne j) 
    Sortie: liste de listes des alignements optimaux des séquences"""
 
    """if i != 1:
        if j != 1:
            if T[i, j] == T[i-1,j-1] + Sub(x[i-2], y[j-2]):
                Alignement(x, y, i-1, j-1, T)
            elif T[i, j] == T[i-1, j] + Del(x[i-2]):
                Alignement(x, y, i-1, j, T)
            else:
                Alignement(x, y, i, j-1, T)
        else:
            Alignement(x, y, i-1, 1, T)
    else:
        if j != 1:
            Alignement(x, y, 1, j-1, T)"""
 
    c = [0]*3
 
    #Copie de L
    M =  deepcopy(L) 
 
    if i != 1:
        if j != 1:
            if T.getitem(i, j) == T.getitem(i-1,j-1) + Sub(x[i-2], y[j-2]):
                c[0] = 1
                L = M + [[x[i-2], y[j-2]]]
                Alignement(x, y, i-1, j-1, T, L)
                print L
                print "ok1"
            elif T.getitem(i, j) == T.getitem(i-1, j) + Del(x[i-2]):
                c[1] = 1
                if sum(c) == 1:
                    L = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L)
                    print L
                else:
                    compteur += 1
                    L[compteur] = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L[compteur])
                    print L[compteur]
            else:
                c[2] = 1
                if sum(c) == 1:
                   L = M +  [['-', y[j-2]]]
                   Alignement(x, y, i, j-1, T, L)
                   print L
                   print "ok2"
                elif sum(c) == 2:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    print L[compteur]
                    print "ok3"
                else:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    print L[compteur]
        else:
            L = M + [[x[i-2], '-']]
            Alignement(x, y, i-1, 1, T, L)
            print L
    else:
        if j != 1:
            L = M +  [['-', y[j-2]]]
            Alignement(x, y, 1, j-1, T, L)
            print L
    return M
 
 
if __name__ == "__main__":
    seq1 = 'YWCQPGK' 
    seq2 = 'LAWYQQKPGKA'
    m = len(seq1)
    n = len(seq2)
    T = Matrice_cout(seq1, seq2)
    L = Alignement(seq1, seq2, m+1, n+1, T, [])
    print L

Cela ne fait pas du tout ce que je veux.
Quelqu'un aurait une piste, svp?
Merci d'avance

[nyko77]

Bonjour,
Je ne suis pas sûr de bien comprendre ce que tu veux faire et je ne suis pas très fort en math, mais je pense que tu peux regarder du coté de numpy, c'est pratique pour gérer des matrices.
Je ne crois pas que ce soit ce que tu veux mais voici un exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
import numpy
 
#matrice de depart
matrice = numpy.array([(5,2,1,4), (2,3,8,9), (5,3,5,8), (1,0,8,7)])
#matrice du resultat
matriceOut = numpy.zeros((matrice.shape))
 
#recopie la ligne 0 et la colonne 0 dans la matrice resultat
matriceOut[0, :] = matrice[0, :]
matriceOut[:, 0] = matrice[:, 0]
 
#boucle la matrice
for i in range(1, matrice.shape[0]):
	for j in range(1, matrice.shape[1]):
		#stock le resultat
		matriceOut[i, j] = min(matrice[i-1, j], matrice[i, j-1], matrice[i-1, j-1])
 
 
print matrice
print matriceOut

[lilly74]

Bonjour,
tout d'abord, merci Nyko77: je ne connaissais pas, je m'en servirais peut-être
Malheureusement, cela ne répond pas à ma question qui est sûrement très confuse
En fait, en arrangeant le code, j'ai la sortie que je veux mais ce n'est pas très "propre".
En effet, pour :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
compteur = 0
 
def Alignement(x, y, i, j, T, L):
    """Prend en entrée les deux séquences à aligner,
    la matrice des couts,
    et la position actuelle dans la matrice des couts
    (ligne i, colonne j) 
    Sortie: liste de listes des alignements optimaux des séquences"""
 
    global compteur
    c = [0]*3
    maxi=max(len(x), len(y))
 
    #Copie de L
    M =  deepcopy(L) 
 
    if i != 1:
        if j != 1:
            if T.getitem(i, j) == T.getitem(i-1,j-1) + Sub(x[i-2], y[j-2]):
                c[0] = 1
                L = M + [[x[i-2], y[j-2]]]
                Alignement(x, y, i-1, j-1, T, L)
                if len(L)==maxi:
                    print L[::-1]
            if T.getitem(i, j) == T.getitem(i-1, j) + Del(x[i-2]):
                c[1] = 1
                if sum(c) == 1:
                    L = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L)
                    if len(L)==maxi:
                        print L[::-1]
                else:
                    compteur += 1
                    L[compteur] = M + [[x[i-2], '-']]
                    Alignement(x, y, i-1, j, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
            if T.getitem(i, j) == T.getitem(i, j-1) + Ins(y[i-2]):
                c[2] = 1
                if sum(c) == 1:
                   L = M +  [['-', y[j-2]]]
                   Alignement(x, y, i, j-1, T, L)
                   if len(L)==maxi:
                       print L[::-1]
                elif sum(c) == 2:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
                else:
                    compteur += 1
                    L[compteur] = M + [['-', y[j-2]]]
                    Alignement(x, y, i, j-1, T, L[compteur])
                    if len(L[compteur])==maxi:
                        print L[compteur][::-1]
        else:
            L = M + [[x[i-2], '-']]
            Alignement(x, y, i-1, 1, T, L)
            if len(L)==maxi:
                print L[::-1]
    else:
        if j != 1:
            L = M +  [['-', y[j-2]]]
            Alignement(x, y, 1, j-1, T, L)
            if len(L)==maxi:
                print L[::-1]
    return M
 
 
if __name__ == "__main__":
    seq1 = 'YWCQPGK' 
    seq2 = 'LAWYQQKPGKA'
    m = len(seq1)
    n = len(seq2)
    T = Matrice_cout(seq1, seq2)
    L = Alignement(seq1, seq2, m+1, n+1, T, [])

j'ai L=[] à la fin, alors qu'il me semble que je le remplis
Je dois passer à côté de la récursivité...
Si quelqu'un pouvait, svp, m'expliquer pourquoi lorsque je remplis une liste, les sorties "au fur et à mesure" sont correctes mais en ordre inversé (par rapport à ma logique)?
Merci d'avance

[eyquem]

Bonjour,


Pourrais tu donner de l'information permettant de faire tourner ton code stp.
Il manque au moins la connaissance de la matrice des coûts de départ pour cela.