Solution: String Alignments in Darwin

Problem 1

CreateDayMatrices(); 
Set(printgc=false); 

s := 'NMTTSRQLLFTFFFTTTFFFFFFQARGLPCSPTWC'; 
t := 'NQLLFTFFTTTFFFFQAGLRSAA':
a := Align(s,t,Local, DMS); 

for i to 250 by 5 do 
   dm := SearchDayMatrix(i,DMS):
   a := Align(s,t,Global,dm):
   printf('PAM dist = %5.2f, Score = %5.2f\n', i, a[Score]):
od: 

PAM dist =  1.00, Score =  9.23
PAM dist =  6.00, Score = 30.47
PAM dist = 11.00, Score = 42.02
PAM dist = 16.00, Score = 50.77
PAM dist = 21.00, Score = 55.89
PAM dist = 26.00, Score = 59.27
PAM dist = 31.00, Score = 61.27
PAM dist = 36.00, Score = 62.42
PAM dist = 41.00, Score = 62.89
PAM dist = 46.00, Score = 62.88
PAM dist = 51.00, Score = 62.49
PAM dist = 56.00, Score = 61.81
PAM dist = 61.00, Score = 60.89
PAM dist = 66.00, Score = 59.78
PAM dist = 71.00, Score = 58.50
PAM dist = 76.00, Score = 57.09
PAM dist = 81.00, Score = 55.56
PAM dist = 86.00, Score = 53.95
PAM dist = 91.00, Score = 52.26
PAM dist = 96.00, Score = 50.50
PAM dist = 101.00, Score = 48.70
PAM dist = 106.00, Score = 46.85
PAM dist = 111.00, Score = 44.96
PAM dist = 116.00, Score = 43.05
PAM dist = 121.00, Score = 41.12
PAM dist = 126.00, Score = 39.18
PAM dist = 131.00, Score = 37.22
PAM dist = 136.00, Score = 35.26
PAM dist = 141.00, Score = 33.31
PAM dist = 146.00, Score = 31.35
PAM dist = 151.00, Score = 29.40
PAM dist = 156.00, Score = 27.46
PAM dist = 161.00, Score = 25.53
PAM dist = 166.00, Score = 23.62
PAM dist = 171.00, Score = 21.72
PAM dist = 176.00, Score = 19.85
PAM dist = 181.00, Score = 17.99
PAM dist = 186.00, Score = 16.16
PAM dist = 191.00, Score = 14.64
PAM dist = 196.00, Score = 13.22
PAM dist = 201.00, Score = 11.81
PAM dist = 206.00, Score = 10.42
PAM dist = 211.00, Score =  9.05
PAM dist = 216.00, Score =  7.70
PAM dist = 221.00, Score =  6.36
PAM dist = 226.00, Score =  5.04
PAM dist = 231.00, Score =  3.75
PAM dist = 236.00, Score =  2.47
PAM dist = 241.00, Score =  1.22
PAM dist = 246.00, Score = -0.01

The score changes depending on which Dayhoff matrix was used for the alignment. The highest score is reached for the 41 PAM matrix. The list suggest that the maximum would be between 41 and 46 PAM.

Using DMS as the matrix argument of Align, will cause Darwin to automatically find the best matrix out of all matrices saved in DMS:

   a := Align(s,t,Global,DMS):
   print(a);

lengths=35,23 simil=62.9, PAM_dist=43.0647, identity=51.4%
NMTTSRQLLFTFFFTTTFFFFFFQARGLPCSPTWC
|     ||||||| ||   |||||| ||..:   .
N_____QLLFTFFTTT___FFFFQA_GLRSA___A

The optimal score for the alignement of s and t is 43.0647 PAM. The score compares the likelihood of the two sequences stemming from a common ancester at a distance d to the likelihood of the sequences being paired by chance. Since the later is independent of d, finding the optimal PAM matrix corresponds to a maximum-likelihood estimation of of the PAM distance d between the sequences.

Problem 2 

CreateDayMatrices(); 
ReadDb('/home/darwin/DB/Problem2.db'); 

e := Entry(651); # get entry number 651
print(e);

ID   BMRB_CHICK
AC   Q05438;
DE   Bone morphogenetic protein receptor type IB precursor (EC 2.7.1.37) (Serine/threonine-protein kinase receptor R6) (SKR6) (Activin receptor-like kinase 6) (ALK-6) (RPK-1).
OS   Gallus gallus (Chicken).
OC   Eukaryota; Metazoa; Chordata; Craniata; Vertebrata; Euteleostomi; Archosauria; Aves; Neognathae; Galliformes; Phasianidae; Phasianinae; Gallus.
KW   Receptor; Transferase; Serine/threonine-protein kinase; ATP-binding; Transmembrane; Glycoprotein; Signal.
SEQ MPLLSSSKLSMESRKEDSEGTAPAPPQKKLSCQCHHHCPEDSVNSTCSTDGYCFTIIEEDDSGGHLVTKGCLGLEGSDFQCRDTPIPHQRRSIEC
CTGQDYCNKHLHPTLPPLKNRDFAEGNIHHKALLISVTVCSILLVLIIIFCYFRYKRQEARPRYSIGLEQDETYIPPGESLKDLIEQSQSSGSGSGLPL
LVQRTIAKQIQMVKQIGKGRYGEVWMGKWRGEKVAVKVFFTTEEASWFRETEIYQTVLMRHENILGFIAADIKGTGSWTQLYLITDYHENGSLYDYLKS
TTLDTKGMLKLAYSSVSGLCHLHTGIFSTQGKPAIAHRDLKSKNILVKKNGTCCIADLGLAVKFISDTNEVDIPPNTRVGTKRYMPPEVLDESLNRNHF
QSYIMADMYSFGLILWEIARRCVSGGIVEEYQLPYHDLVPSDPSYEDMREIVCIKRLRPSFPNRWSSDECLRQMGKLMMECWAHNPASRLTALRVKKTL
AKMSESQDIKL

With DB[TotEntries] the total number of entries in the database can be determined. Aligning a sequence against all other entries in a database can take very long. Here, it doen't take too long because we use only the 50 PAM matrix. Alignments using DMS take about 13 times as long. Also, the DB used here is very small. Often, databases contain thousands or even millions of entries.

dm50 := DayMatrix(50);
for i to DB[TotEntries] do
    if i=651 then next fi;
    al := Align(e,Entry(i),dm50);
    if al[Score]>130 then
        de := SearchTag('DE',Entry(i));
        printf('Score = %.1f,  DE = %s\n',al[Score],de);
    fi;
od:

Score = 136.5,  DE = Tyrosine-protein kinase Abl (EC 2.7.1.112) (D-ash).
Score = 130.6,  DE = Proto-oncogene tyrosine-protein kinase YES (EC 2.7.1.112) (P61-YES) (C-YES).
Score = 130.6,  DE = Proto-oncogene tyrosine-protein kinase YES (EC 2.7.1.112) (p61-YES) (C-YES).
Score = 149.6,  DE = Proto-oncogene tyrosine-protein kinase YRK (EC 2.7.1.112) (p60-YRK) (YES related kinase).
Score = 163.3,  DE = Tyrosine-protein kinase CSK (EC 2.7.1.112) (C-SRC kinase).
Score = 168.1,  DE = Tyrosine-protein kinase CSK (EC 2.7.1.112) (C-SRC kinase) (Protein- tyrosine kinase CYL).
Score = 168.1,  DE = Tyrosine-protein kinase CSK (EC 2.7.1.112) (C-SRC kinase) (Protein- tyrosine kinase MPK-2).
Score = 168.1,  DE = Tyrosine-protein kinase CSK (EC 2.7.1.112) (C-SRC kinase).
Score = 172.5,  DE = Tyrosine-protein kinase 2 (EC 2.7.1.112) (Fragment).
Score = 134.8,  DE = Proto-oncogene tyrosine-protein kinase LCK (EC 2.7.1.112) (Protein- tyrosine kinase C-TKL).
Score = 153.4,  DE = Proto-oncogene tyrosine-protein kinase LCK (EC 2.7.1.112) (P56-LCK) (LSK) (T cell-specific protein-tyrosine kinase).
Score = 154.9,  DE = Proto-oncogene tyrosine-protein kinase LCK (EC 2.7.1.112) (P56-LCK) (LSK).
Score = 138.5,  DE = Tyrosine-protein kinase LYN (EC 2.7.1.112).
Score = 130.1,  DE = Tyrosine-protein kinase LYN (EC 2.7.1.112).
Score = 155.2,  DE = Serine/threonine-protein kinase transforming protein Rmil (EC 2.7.1.37).
Score = 155.2,  DE = Serine/threonine-protein kinase transforming protein Rmil (EC 2.7.1.37).
Score = 131.8,  DE = Tyrosine-protein kinase SRC-2 (EC 2.7.1.112) (p60-SRC-2).
Score = 131.8,  DE = Tyrosine-protein kinase transforming protein SRC (EC 2.7.1.112) (P60- SRC).
Score = 131.8,  DE = Tyrosine-protein kinase transforming protein SRC (EC 2.7.1.112) (P60- SRC).
Score = 132.0,  DE = Tyrosine-protein kinase transforming protein SRC (EC 2.7.1.112) (P60- SRC).
Score = 131.8,  DE = Tyrosine-protein kinase transforming protein SRC (EC 2.7.1.112) (P60- SRC).
Score = 131.8,  DE = Proto-oncogene tyrosine-protein kinase SRC (EC 2.7.1.112) (p60-SRC) (C-SRC).
Score = 145.1,  DE = Proto-oncogene tyrosine-protein kinase SRC (EC 2.7.1.112) (p60-SRC) (C-SRC).
Score = 137.3,  DE = Neuronal proto-oncogene tyrosine-protein kinase SRC (EC 2.7.1.112) (p60-SRC) (C-SRC).
Score = 137.2,  DE = Proto-oncogene tyrosine-protein kinase SRC (EC 2.7.1.112) (p60-SRC) (C-SRC).
Score = 136.5,  DE = Tyrosine-protein kinase isoform SRK1 (EC 2.7.1.112).
Score = 136.3,  DE = Tyrosine-protein kinase SRK2 (EC 2.7.1.112) (Fragment).
Score = 165.2,  DE = Proto-oncogene tyrosine-protein kinase FYN (EC 2.7.1.112) (P59-FYN) (SYN) (SLK).
Score = 160.2,  DE = Proto-oncogene tyrosine-protein kinase FYN (EC 2.7.1.112) (P59-FYN).
Score = 191.8,  DE = Proto-oncogene tyrosine-protein kinase FYN (EC 2.7.1.112) (P59-FYN).
Score = 147.1,  DE = A-Raf proto-oncogene serine/threonine-protein kinase (EC 2.7.1.-) (A-raf-1) (Proto-oncogene Pks).
Score = 147.1,  DE = A-Raf proto-oncogene serine/threonine-protein kinase (EC 2.7.1.-).
Score = 147.1,  DE = A-Raf proto-oncogene serine/threonine-protein kinase (EC 2.7.1.-) (A-Raf-1).
Score = 147.1,  DE = A-Raf proto-oncogene serine/threonine-protein kinase (EC 2.7.1.-).

We were searching for proteins with a similar sequence to Entry(651). Similar sequence often implies similar function. This is confirmed as all results appear to have somethign to do with tyrosine kinase.