Use the supplied BLOSUM62 entry for every diagonal move in the Smith-Waterman algorithm, while retaining the stipulated linear gap penalty of . If and are the current amino acids, the dynamic programming recurrence isThe zero option permits a new local start. The following original implementation also records the traceback coordinates needed in part (c); its tie ordering is left, up, diagonal, and an equal overall maximum replaces the previous best cell, as in the supplied convention:
def local_alignment(query,reference,alphabet,scores,gap=-1):
lookup={aa:i for i,aa in enumerate(alphabet)}
table=np.asarray(scores,dtype=int)
height,width=len(query)+1,len(reference)+1
H=np.zeros((height,width),dtype=int)
back=np.zeros((height,width),dtype=np.int8)
best=(0,0,0)
for i,a in enumerate(query,1):
for j,b in enumerate(reference,1):
# Order implements the printed LEFT, UP, DIAGONAL tie priority.
candidates=(0,H[i,j-1]+gap,H[i-1,j]+gap,
H[i-1,j-1]+int(table[lookup[a],lookup[b]]))
value=max(candidates);H[i,j]=value
back[i,j]=0 if value==0 else candidates.index(value)
if value>=best[0]:best=(value,i,j)
score,i,j=best;query_end,ref_end=i,j
aq=[];ar=[]
while H[i,j]>0:
step=back[i,j]
if step==1:aq.append('-');ar.append(reference[j-1]);j-=1
elif step==2:aq.append(query[i-1]);ar.append('-');i-=1
elif step==3:aq.append(query[i-1]);ar.append(reference[j-1]);i-=1;j-=1
qa=''.join(reversed(aq));ra=''.join(reversed(ar));length=len(qa)
identities=sum(a==b and a!='-' for a,b in zip(qa,ra))
similarities=sum(a!='-' and b!='-' and table[lookup[a],lookup[b]]>0 for a,b in zip(qa,ra))
gaps=sum(a=='-' or b=='-' for a,b in zip(qa,ra))
return dict(query=qa,reference=ra,score=int(score),query_start=i+1,query_end=query_end,
reference_start=j+1,reference_end=ref_end,query_length=len(query),reference_length=len(reference),
alignment_length=length,identities=int(identities),similarities=int(similarities),gaps=int(gaps),
identity_percent=100*identities/length if length else 0.,
similarity_percent=100*similarities/length if length else 0.,gap_percent=100*gaps/length if length else 0.)
queries = {"baboon": baboon, "squirrel_monkey": squirrel_monkey,
"dingo": dingo, "goldfish": goldfish}
alignments = {
name: local_alignment(seq, reference_epo_receptor_human, amino_acids, bmat)
for name, seq in queries.items()
}
for name, result in alignments.items():
print(name, "score", result["score"])
print(result["query"])
print(result["reference"])The resulting local sequence alignments, with the query above the reference, are:
baboon; score 314
SLLTPSDLDPLILTLSLILVLIVVLLTVLALLSHRRALKQKIWPGIPSPESEFEGLFTTHKG-FQL
SLLTPSDLDPLILTLSLILVVILVLLTVLALLSHRRALKQKIWPGIPSPESEFEGLFTTHKGNFQLsquirrel monkey; score 278
VCFWEEAASAGMGPDNYSFSYQL-DNEPWKR-CRLHQTPTARGVVRFWCSLPRADTSS
VCFWEEAASAGVGPGNYSFSYQLED-EPWK-LCRLHQAPTARGAVRFWCSLPTADTSSdingo; score 301
MNHLW--THLWPG-VGSLCLLLAGAAWASLPKP-L-DPKFESKAALLAARAPEELLCFTERLEDLVCFWEE
MDHL-GAS-LWP-QVGSLCLLLAGAAWAP-P-PNLPDPKFESKAALLAARGPEELLCFTERLEDLVCFWEEgoldfish; score 190
L--LVLSIGLILC--L-LSLTVI-L-SHQKFLLK-KLWPDIPTPEHKFPGLFTVYKGDFKE-WMSH-NNGSM
LDPLILTLSLILVVILVL-LTVLALLSHRR-ALKQKIWPGIPSPESEFEGLFTTHKGNF-QLWL-YQNDGCLThe several short gaps are a consequence of the specified inexpensive linear gap penalty; substituting a different default or an affine gap penalty would solve a different scoring problem.
Use the number of alignment columns, including gap columns, as the denominator. A column contributes to sequence identity when its two nongap letters are equal, to sequence similarity when its two nongap letters have a strictly positive BLOSUM62 score, and to the gap fraction when either letter is a gap. A zero substitution score is not counted as similar.
The implementation in part (a) computes each numerator directly during its final pass through the aligned strings:
for name, a in alignments.items():
print(name, a["alignment_length"], a["identities"],
a["similarities"], a["gaps"])
print(a["identity_percent"], a["similarity_percent"], a["gap_percent"])Identical columns also count as similar for these data, so these percentages are overlapping summaries rather than three categories summing to 100%.
The maximum-scoring cell records the inclusive end position in each sequence. During traceback, moving left consumes a reference residue, moving up consumes a query residue, and moving diagonally consumes both; when traceback stops, the remaining prefix lengths are one less than the corresponding one-based starts. Consequently
i+1 and j+1 are the correct starts returned in part (a), without counting any inserted gaps as sequence residues.The following report joins these coordinates to the alignments and sequence identity/sequence similarity values already calculated:
for name, a in alignments.items():
print(f"{name}: query length={a['query_length']}, "
f"reference length={a['reference_length']}, "
f"alignment columns={a['alignment_length']}, score={a['score']}")
print(f"Query {a['query_start']} {a['query']} {a['query_end']}")
print(f"Ref {a['reference_start']} {a['reference']} {a['reference_end']}")
print(f"Identity {a['identity_percent']:.2f}%; "
f"similarity {a['similarity_percent']:.2f}%; "
f"gaps {a['gap_percent']:.2f}%")All reference sequences have length 508. The following are one-based inclusive coordinates; the aligned strings and all percentages are given in parts (a) and (b).
Articles by others on the same topic
There are currently no matching articles.