traceback (was [Biophp-dev] scripts)

[biophp-dev@bioinformatics.org]

------------EDA71A98306DE3
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Hola serge,


SG> Your code seems to be working fine.  I'll
SG> do more tests on it.  Btw, could you be more specific as to
SG>  what you were looking for last time?  The traceback thing?
SG> I might have some links for you...
from what i've learned so far alignment can be done by variuous
algorithms, needleman-wunsch being the most basic one described on the
site u linked to in a recent mail.
(http://molvis.chem.indiana.edu/C687_S99/lecture2.html#alignments)
All of them seem to be related, just varying in the different cost
models they use.
The traceback step comes after filling the matrix with the different
costs for transformations, starting in the lower right corner one
traces the possible alignments back to the upper left corner, by
going up, left, or diagonal to where the lowest cell values are and
diagonal having priority over the others. It is perfectly escribed in
this article which uses a matrix build out of the levensthein
distance.
http://bioinfo.weizmann.ac.il/courses/BCG/lectures/02_pairwise/2.4tools/03DP.html

Until now im not quite sure if the traceback process is the same in
all those different global alignment algorithms, i might not know ;)
If yes, one could have one single traceback function for all the different
algorithms.
Thats why im looking for material regarding the different algorithms, the
ones i found where needleman-wunsch, smith-waterman and some
extensions of them, which seem to share the Traceback procedure.

i attached a very basic bit that returns a matrix as a result of a
needleman-wunsch algorithm which could be passed to a traceback
function doing the actual alignment. Of course its gotta be oo in the
end, but i did tell u im lazy ;)
------------EDA71A98306DE3
Content-Type: application/octet-stream; name="alignabit.inc.php"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="alignabit.inc.php"

PD9waHANCmZ1bmN0aW9uIG5lZWRsZW1hbl93dW5zY2hfbWF0cml4KCRzb3VyY2UsJHRhcmdldCl7
DQoJJG1hdHJpeD1hcnJheShyYW5nZSgwLHN0cmxlbigkc291cmNlKS0xKSxyYW5nZSgwLHN0cmxl
bigkdGFyZ2V0KS0xKSk7DQoJLy9pbml0aWFsaXplIG1hdHJpeA0KCWZvciAoJGk9MDskaTw9c3Ry
bGVuKCRzb3VyY2UpOyRpKyspIHsNCgkJJG1hdHJpeFskaV1bMF09MDsNCgl9DQoJZm9yKCRqPTA7
JGo8PXN0cmxlbigkdGFyZ2V0KTskaisrKSB7DQoJCSRtYXRyaXhbMF1bJGpdPTA7DQoJfQ0KCQ0K
CWZvciAoJGk9MTskaTw9c3RybGVuKCRzb3VyY2UpOyRpKyspIHsNCgkJZm9yKCRqPTE7JGo8PXN0
cmxlbigkdGFyZ2V0KTskaisrKSB7DQoJCQlpZiAoJHNvdXJjZVskaS0xXT09JHRhcmdldFskai0x
XSkgew0KCQkJCSRtYXRyaXhbJGldWyRqXT1tYXgoJG1hdHJpeFskaV1bJGotMV0sJG1hdHJpeFsk
aS0xXVskal0sJG1hdHJpeFskaS0xXVskai0xXSsxKTsNCgkJCX1lbHNlew0KCQkJCSRtYXRyaXhb
JGldWyRqXT1tYXgoJG1hdHJpeFskaV1bJGotMV0sJG1hdHJpeFskaS0xXVskal0sJG1hdHJpeFsk
aS0xXVskai0xXSk7DQoJCQl9DQoJCX0NCgl9DQoNCgkvL2VjaG8gbWF0cml4DQoJZWNobyAiICAg
ICAgICI7DQoJZm9yICgkaT0wOyRpPHN0cmxlbigkdGFyZ2V0KTskaSsrKXsNCgkJZWNobyAiICIu
JHRhcmdldFskaV0uIiAgIjsNCgl9DQoJZWNobyAiXG4gIjsNCglmb3IgKCRpPTA7JGk8PXN0cmxl
bigkdGFyZ2V0KTskaSsrKSB7DQoJCWVjaG8gIiAgIDAiOw0KCX0NCgllY2hvICJcbiI7DQoJZm9y
ICgkaT0xOyRpPD1zdHJsZW4oJHNvdXJjZSk7JGkrKykgew0KCQllY2hvICRzb3VyY2VbJGktMV07
DQoJCWZvcigkaj0wOyRqPD1zdHJsZW4oJHRhcmdldCk7JGorKykgew0KCQkJcHJpbnRmKCIlNGQi
LCRtYXRyaXhbJGldWyRqXSk7DQoJCX0NCgkJZWNobyAiXG4iOw0KCX0NCglyZXR1cm4gJG1hdHJp
eDsNCn0NCg0KbmVlZGxlbWFuX3d1bnNjaF9tYXRyaXgoIkdHQVRDR0EiLCJHQUFUVENBR1RUQSIp
Ow0KPz4=

------------EDA71A98306DE3--