pour faire cet algo je procede en construisant un tableau qui donne les longueurs des plus longues sous chaines communes des sous-chaines  
 
, determinees par les indices du tableau, puis en lisant la derniere ligne il est facile de reconstituer la plus longue sous  
 
chaine. Je suis ptet pas super clair mais sans doute ceux qui connaissent cet algorithme me comprendront
 

 
la question est : c'est une complexité m x n ,c'est pas si mal, mais en memoire ca bouffe bcp. En fait il n'est pas  
 
nécessaire de sauvegarder tout le tableau, donc je peux ne sauvegarder que la derniere colonne remplie a chaque fois, ca fera  
 
une belle optimisation de memoire (m+n au lieu de m*n).  
Sinon Y a t-il un autre algo plus effiace que m*n ( nivo complexite, pas memoire)?
 
mon code, sous license GPL

je regarde l'alog, mais niveau implémentation, y a du boulot!

je sais. LA c'est l'étape : "ca marche".
 
ensuite, je pase à l'étape : "çai bô" et "çai rapide"

putain, sur google, y a plein de resultat avec ton algo en m*, mais des fois est evoqué un algo en temps pseudo linéaire

J'ai trouvé une page qui pourrait peut-être t'intéressé :
 
http://www.crpgl.lu/cortina/Details/LCS.html
 
Je n'ai pas apercu de calcul complexité, mais ca semble balayer pas mal de type de solutions !
 
 
@+

c'est le meme aglo qui est expliqué

Ok, je sors.

http://www.csse.monash.edu.au/~llo [...] 6.IPL.html
 
meme algo, à un truc pres, qui donne un bon boost apparemment

 
merci bien, je sens que je v passer un bon bout de temps là-dessus  le comprendre. De la m^me maniere qu'il a fallut qq heures pour comprendre mon algo qui s'implémente en qq misérables   lignes de code

bon la j'ai compris  ou était l'astuce, masi j'ai pas encore compris pourquoi effectivement ca marchait
 

 
je comprend que la c genial, mais je comprend pas pkoi
 
 
par la suite, y'a encore 2-3 optimsation que je dois comprendre, mé c pas facile

ben comme toutes les optimsiations aggressives, c'est cahud...
 
quand t'auras besoin de conseil d'implémentation, n'hesite pas

bon, la g compris ce qu'il faillait faire, mais je demande que le taré qui a mis au point cette technique soit interné en maison de repos.    
 
 
sinon, nivo implémentation, je vois pas ce que tu me reproches ? ( sans doute as-tu raison mais je suis aveugle)

y'a juste son point 2.3 ke je capte pas, pour prendre une LCS il suffit de lire la dernière ligne, et pourtant lui il fait une technique super compliquée...

doit y avoir un moyen d'améliorer les choses si les chaines sont pas de meme longueur  

pour ce qui est de de trouver une PLSC, il suffit de "lire" une dernieres ligne ou colonne

en tout cas je sais pas si tu as vu, mais avec seulement les 2 dernières lignes, on fait tout le boulot sans problèmes

hey, mais j'ai bien l'impression que l'algo foire dis-donc?

 
Non, la complexite restera de l'ordre m*n.

lekel ?

vivi, puis qu'elles indiquent les lettres a prendre dans l'autre chaine pour former la PLSC

ben regarde ton exemple

 
bah il est coherent.

abcdefghijkl abbcdfghj
 
 
abcdfghj n'est pas dans abcdefghijkl  
abcdfghj n'est pas dans abbcdfghj
 
c'est pas ce que j'appelle etre en "commun"

tu ne connais pas le probleme
 
en fait ce probleme de plsc c'est la plus longue sous chaine obtenue en supprimant si necessaires de elements de la chaine 1 ou 2, c'est pour cela que ca devient interessant, avec ta definition c trivial
 
( application : diff, en considerant qu'une ligne de code est un symbole )

avec ma definition c'est pas trivial, mais la tienne je la comprends pas, on dirait l'interesction d'ensemble

avec ta définition ca se fait de maniere quasi-linéraire
 
moi c'est la plus longue sous chaine commune en supprimant des élements
 
application : tu veux comparer deux chaines d'adn, une originale et une mutée. la mutée, elle aura des segments insérés, supprimes, ou remplacés. masi grace a l'algo tu retrouve la plsu longue chaien commune.

 
Et  la je pense qu'il n'y a plus de probleme de "definition".

le probleme c'est qu'on l'appelle plsc

Ce qui est qualifie de sous chaine ici est en fait la plus longue chaine commune possible avec gaps:
En reprenant ton exemple:
 

__avec__ des gaps... la notion de chaine/sequence en prends un coup... mais si ça te satisfait  

Sans gaps, on ne s'en sort pas dans les sequences biologiques. Par contre cette maniere de faire n'est absolument pas interressante pour trouver des alignements biologiquement satisfaisants.