| 1 |
""" |
| 2 |
Collection of sequence alignment algorithms. |
| 3 |
|
| 4 |
@note: The classes in this module have been optimized for performance. |
| 5 |
Think twice before switching a field to a generally nicer property |
| 6 |
access, because it turns out that these things often add significant |
| 7 |
constants to the running time of a dynamic programming algorithm. |
| 8 |
""" |
| 9 |
|
| 10 |
from csb.bio.sequence import AbstractSequence, SequenceAlignment, RichSequence, ResidueInfo |
| 11 |
from abc import ABCMeta, abstractmethod |
| 12 |
|
| 13 |
|
| 14 |
class ResidueNotFoundError(KeyError): |
| 15 |
pass |
| 16 |
|
| 17 |
|
| 18 |
class AbstractScoringMatrix(object): |
| 19 |
""" |
| 20 |
Defines a pairwise sequence alignment scoring function. |
| 21 |
""" |
| 22 |
|
| 23 |
__metaclass__ = ABCMeta |
| 24 |
|
| 25 |
@abstractmethod |
| 26 |
def score(self, x, y): |
| 27 |
""" |
| 28 |
Return the pairwise score of residues C{x} and C{y}. |
| 29 |
C{x} and C{y} must be comparable (e.g. implement __eq__ and __hash__). |
| 30 |
|
| 31 |
@param x: first residue |
| 32 |
@type x: object |
| 33 |
@param y: second residue |
| 34 |
@type y: object |
| 35 |
|
| 36 |
@rtype: float |
| 37 |
|
| 38 |
@raise ResidueNotFoundError: if C{x} or C{y} cannot be handled by this |
| 39 |
scoring matrix |
| 40 |
""" |
| 41 |
pass |
| 42 |
|
| 43 |
class IdentityMatrix(AbstractScoringMatrix): |
| 44 |
""" |
| 45 |
Simple identity-based scoring matrix. |
| 46 |
|
| 47 |
@param match: score for a match |
| 48 |
@type match: float |
| 49 |
@param mismatch: score for a mismatch |
| 50 |
@type mismatch: float |
| 51 |
""" |
| 52 |
|
| 53 |
def __init__(self, match=1, mismatch=-1): |
| 54 |
|
| 55 |
self._match = float(match) |
| 56 |
self._mismatch = float(mismatch) |
| 57 |
|
| 58 |
@property |
| 59 |
def match(self): |
| 60 |
""" |
| 61 |
Score for a match |
| 62 |
@rtype: float |
| 63 |
""" |
| 64 |
return self._match |
| 65 |
|
| 66 |
@property |
| 67 |
def mismatch(self): |
| 68 |
""" |
| 69 |
Score for a mismatch |
| 70 |
@rtype: float |
| 71 |
""" |
| 72 |
return self._mismatch |
| 73 |
|
| 74 |
def score(self, x, y): |
| 75 |
|
| 76 |
if x == y: |
| 77 |
return self._match |
| 78 |
else: |
| 79 |
return self._mismatch |
| 80 |
|
| 81 |
class SimilarityMatrix(AbstractScoringMatrix): |
| 82 |
""" |
| 83 |
Similarity scoring matrix. |
| 84 |
|
| 85 |
@param matrix: |
| 86 |
""" |
| 87 |
|
| 88 |
BLOSUM62 = { |
| 89 |
'A': { 'A': 4.0, 'R':-1.0, 'N':-2.0, 'D':-2.0, 'C': 0.0, 'Q':-1.0, 'E':-1.0, 'G': 0.0, 'H':-2.0, 'I':-1.0, 'L':-1.0, 'K':-1.0, 'M':-1.0, 'F':-2.0, 'P':-1.0, 'S': 1.0, 'T': 0.0, 'W':-3.0, 'Y':-2.0, 'V': 0.0, 'B':-2.0, 'Z':-1.0, 'X': 0.0, '*':-4.0 }, |
| 90 |
'R': { 'A':-1.0, 'R': 5.0, 'N': 0.0, 'D':-2.0, 'C':-3.0, 'Q': 1.0, 'E': 0.0, 'G':-2.0, 'H': 0.0, 'I':-3.0, 'L':-2.0, 'K': 2.0, 'M':-1.0, 'F':-3.0, 'P':-2.0, 'S':-1.0, 'T':-1.0, 'W':-3.0, 'Y':-2.0, 'V':-3.0, 'B':-1.0, 'Z': 0.0, 'X':-1.0, '*':-4.0 }, |
| 91 |
'N': { 'A':-2.0, 'R': 0.0, 'N': 6.0, 'D': 1.0, 'C':-3.0, 'Q': 0.0, 'E': 0.0, 'G': 0.0, 'H': 1.0, 'I':-3.0, 'L':-3.0, 'K': 0.0, 'M':-2.0, 'F':-3.0, 'P':-2.0, 'S': 1.0, 'T': 0.0, 'W':-4.0, 'Y':-2.0, 'V':-3.0, 'B': 3.0, 'Z': 0.0, 'X':-1.0, '*':-4.0 }, |
| 92 |
'D': { 'A':-2.0, 'R':-2.0, 'N': 1.0, 'D': 6.0, 'C':-3.0, 'Q': 0.0, 'E': 2.0, 'G':-1.0, 'H':-1.0, 'I':-3.0, 'L':-4.0, 'K':-1.0, 'M':-3.0, 'F':-3.0, 'P':-1.0, 'S': 0.0, 'T':-1.0, 'W':-4.0, 'Y':-3.0, 'V':-3.0, 'B': 4.0, 'Z': 1.0, 'X':-1.0, '*':-4.0 }, |
| 93 |
'C': { 'A': 0.0, 'R':-3.0, 'N':-3.0, 'D':-3.0, 'C': 9.0, 'Q':-3.0, 'E':-4.0, 'G':-3.0, 'H':-3.0, 'I':-1.0, 'L':-1.0, 'K':-3.0, 'M':-1.0, 'F':-2.0, 'P':-3.0, 'S':-1.0, 'T':-1.0, 'W':-2.0, 'Y':-2.0, 'V':-1.0, 'B':-3.0, 'Z':-3.0, 'X':-2.0, '*':-4.0 }, |
| 94 |
'Q': { 'A':-1.0, 'R': 1.0, 'N': 0.0, 'D': 0.0, 'C':-3.0, 'Q': 5.0, 'E': 2.0, 'G':-2.0, 'H': 0.0, 'I':-3.0, 'L':-2.0, 'K': 1.0, 'M': 0.0, 'F':-3.0, 'P':-1.0, 'S': 0.0, 'T':-1.0, 'W':-2.0, 'Y':-1.0, 'V':-2.0, 'B': 0.0, 'Z': 3.0, 'X':-1.0, '*':-4.0 }, |
| 95 |
'E': { 'A':-1.0, 'R': 0.0, 'N': 0.0, 'D': 2.0, 'C':-4.0, 'Q': 2.0, 'E': 5.0, 'G':-2.0, 'H': 0.0, 'I':-3.0, 'L':-3.0, 'K': 1.0, 'M':-2.0, 'F':-3.0, 'P':-1.0, 'S': 0.0, 'T':-1.0, 'W':-3.0, 'Y':-2.0, 'V':-2.0, 'B': 1.0, 'Z': 4.0, 'X':-1.0, '*':-4.0 }, |
| 96 |
'G': { 'A': 0.0, 'R':-2.0, 'N': 0.0, 'D':-1.0, 'C':-3.0, 'Q':-2.0, 'E':-2.0, 'G': 6.0, 'H':-2.0, 'I':-4.0, 'L':-4.0, 'K':-2.0, 'M':-3.0, 'F':-3.0, 'P':-2.0, 'S': 0.0, 'T':-2.0, 'W':-2.0, 'Y':-3.0, 'V':-3.0, 'B':-1.0, 'Z':-2.0, 'X':-1.0, '*':-4.0 }, |
| 97 |
'H': { 'A':-2.0, 'R': 0.0, 'N': 1.0, 'D':-1.0, 'C':-3.0, 'Q': 0.0, 'E': 0.0, 'G':-2.0, 'H': 8.0, 'I':-3.0, 'L':-3.0, 'K':-1.0, 'M':-2.0, 'F':-1.0, 'P':-2.0, 'S':-1.0, 'T':-2.0, 'W':-2.0, 'Y': 2.0, 'V':-3.0, 'B': 0.0, 'Z': 0.0, 'X':-1.0, '*':-4.0 }, |
| 98 |
'I': { 'A':-1.0, 'R':-3.0, 'N':-3.0, 'D':-3.0, 'C':-1.0, 'Q':-3.0, 'E':-3.0, 'G':-4.0, 'H':-3.0, 'I': 4.0, 'L': 2.0, 'K':-3.0, 'M': 1.0, 'F': 0.0, 'P':-3.0, 'S':-2.0, 'T':-1.0, 'W':-3.0, 'Y':-1.0, 'V': 3.0, 'B':-3.0, 'Z':-3.0, 'X':-1.0, '*':-4.0 }, |
| 99 |
'L': { 'A':-1.0, 'R':-2.0, 'N':-3.0, 'D':-4.0, 'C':-1.0, 'Q':-2.0, 'E':-3.0, 'G':-4.0, 'H':-3.0, 'I': 2.0, 'L': 4.0, 'K':-2.0, 'M': 2.0, 'F': 0.0, 'P':-3.0, 'S':-2.0, 'T':-1.0, 'W':-2.0, 'Y':-1.0, 'V': 1.0, 'B':-4.0, 'Z':-3.0, 'X':-1.0, '*':-4.0 }, |
| 100 |
'K': { 'A':-1.0, 'R': 2.0, 'N': 0.0, 'D':-1.0, 'C':-3.0, 'Q': 1.0, 'E': 1.0, 'G':-2.0, 'H':-1.0, 'I':-3.0, 'L':-2.0, 'K': 5.0, 'M':-1.0, 'F':-3.0, 'P':-1.0, 'S': 0.0, 'T':-1.0, 'W':-3.0, 'Y':-2.0, 'V':-2.0, 'B': 0.0, 'Z': 1.0, 'X':-1.0, '*':-4.0 }, |
| 101 |
'M': { 'A':-1.0, 'R':-1.0, 'N':-2.0, 'D':-3.0, 'C':-1.0, 'Q': 0.0, 'E':-2.0, 'G':-3.0, 'H':-2.0, 'I': 1.0, 'L': 2.0, 'K':-1.0, 'M': 5.0, 'F': 0.0, 'P':-2.0, 'S':-1.0, 'T':-1.0, 'W':-1.0, 'Y':-1.0, 'V': 1.0, 'B':-3.0, 'Z':-1.0, 'X':-1.0, '*':-4.0 }, |
| 102 |
'F': { 'A':-2.0, 'R':-3.0, 'N':-3.0, 'D':-3.0, 'C':-2.0, 'Q':-3.0, 'E':-3.0, 'G':-3.0, 'H':-1.0, 'I': 0.0, 'L': 0.0, 'K':-3.0, 'M': 0.0, 'F': 6.0, 'P':-4.0, 'S':-2.0, 'T':-2.0, 'W': 1.0, 'Y': 3.0, 'V':-1.0, 'B':-3.0, 'Z':-3.0, 'X':-1.0, '*':-4.0 }, |
| 103 |
'P': { 'A':-1.0, 'R':-2.0, 'N':-2.0, 'D':-1.0, 'C':-3.0, 'Q':-1.0, 'E':-1.0, 'G':-2.0, 'H':-2.0, 'I':-3.0, 'L':-3.0, 'K':-1.0, 'M':-2.0, 'F':-4.0, 'P': 7.0, 'S':-1.0, 'T':-1.0, 'W':-4.0, 'Y':-3.0, 'V':-2.0, 'B':-2.0, 'Z':-1.0, 'X':-2.0, '*':-4.0 }, |
| 104 |
'S': { 'A': 1.0, 'R':-1.0, 'N': 1.0, 'D': 0.0, 'C':-1.0, 'Q': 0.0, 'E': 0.0, 'G': 0.0, 'H':-1.0, 'I':-2.0, 'L':-2.0, 'K': 0.0, 'M':-1.0, 'F':-2.0, 'P':-1.0, 'S': 4.0, 'T': 1.0, 'W':-3.0, 'Y':-2.0, 'V':-2.0, 'B': 0.0, 'Z': 0.0, 'X': 0.0, '*':-4.0 }, |
| 105 |
'T': { 'A': 0.0, 'R':-1.0, 'N': 0.0, 'D':-1.0, 'C':-1.0, 'Q':-1.0, 'E':-1.0, 'G':-2.0, 'H':-2.0, 'I':-1.0, 'L':-1.0, 'K':-1.0, 'M':-1.0, 'F':-2.0, 'P':-1.0, 'S': 1.0, 'T': 5.0, 'W':-2.0, 'Y':-2.0, 'V': 0.0, 'B':-1.0, 'Z':-1.0, 'X': 0.0, '*':-4.0 }, |
| 106 |
'W': { 'A':-3.0, 'R':-3.0, 'N':-4.0, 'D':-4.0, 'C':-2.0, 'Q':-2.0, 'E':-3.0, 'G':-2.0, 'H':-2.0, 'I':-3.0, 'L':-2.0, 'K':-3.0, 'M':-1.0, 'F': 1.0, 'P':-4.0, 'S':-3.0, 'T':-2.0, 'W': 11.0,'Y': 2.0, 'V':-3.0, 'B':-4.0, 'Z':-3.0, 'X':-2.0, '*':-4.0 }, |
| 107 |
'Y': { 'A':-2.0, 'R':-2.0, 'N':-2.0, 'D':-3.0, 'C':-2.0, 'Q':-1.0, 'E':-2.0, 'G':-3.0, 'H': 2.0, 'I':-1.0, 'L':-1.0, 'K':-2.0, 'M':-1.0, 'F': 3.0, 'P':-3.0, 'S':-2.0, 'T':-2.0, 'W': 2.0, 'Y': 7.0, 'V':-1.0, 'B':-3.0, 'Z':-2.0, 'X':-1.0, '*':-4.0 }, |
| 108 |
'V': { 'A': 0.0, 'R':-3.0, 'N':-3.0, 'D':-3.0, 'C':-1.0, 'Q':-2.0, 'E':-2.0, 'G':-3.0, 'H':-3.0, 'I': 3.0, 'L': 1.0, 'K':-2.0, 'M': 1.0, 'F':-1.0, 'P':-2.0, 'S':-2.0, 'T': 0.0, 'W':-3.0, 'Y':-1.0, 'V': 4.0, 'B':-3.0, 'Z':-2.0, 'X':-1.0, '*':-4.0 }, |
| 109 |
'B': { 'A':-2.0, 'R':-1.0, 'N': 3.0, 'D': 4.0, 'C':-3.0, 'Q': 0.0, 'E': 1.0, 'G':-1.0, 'H': 0.0, 'I':-3.0, 'L':-4.0, 'K': 0.0, 'M':-3.0, 'F':-3.0, 'P':-2.0, 'S': 0.0, 'T':-1.0, 'W':-4.0, 'Y':-3.0, 'V':-3.0, 'B': 4.0, 'Z': 1.0, 'X':-1.0, '*':-4.0 }, |
| 110 |
'Z': { 'A':-1.0, 'R': 0.0, 'N': 0.0, 'D': 1.0, 'C':-3.0, 'Q': 3.0, 'E': 4.0, 'G':-2.0, 'H': 0.0, 'I':-3.0, 'L':-3.0, 'K': 1.0, 'M':-1.0, 'F':-3.0, 'P':-1.0, 'S': 0.0, 'T':-1.0, 'W':-3.0, 'Y':-2.0, 'V':-2.0, 'B': 1.0, 'Z': 4.0, 'X':-1.0, '*':-4.0 }, |
| 111 |
'X': { 'A': 0.0, 'R':-1.0, 'N':-1.0, 'D':-1.0, 'C':-2.0, 'Q':-1.0, 'E':-1.0, 'G':-1.0, 'H':-1.0, 'I':-1.0, 'L':-1.0, 'K':-1.0, 'M':-1.0, 'F':-1.0, 'P':-2.0, 'S': 0.0, 'T': 0.0, 'W':-2.0, 'Y':-1.0, 'V':-1.0, 'B':-1.0, 'Z':-1.0, 'X':-1.0, '*':-4.0 }, |
| 112 |
'*': { 'A':-4.0, 'R':-4.0, 'N':-4.0, 'D':-4.0, 'C':-4.0, 'Q':-4.0, 'E':-4.0, 'G':-4.0, 'H':-4.0, 'I':-4.0, 'L':-4.0, 'K':-4.0, 'M':-4.0, 'F':-4.0, 'P':-4.0, 'S':-4.0, 'T':-4.0, 'W':-4.0, 'Y':-4.0, 'V':-4.0, 'B':-4.0, 'Z':-4.0, 'X':-4.0, '*': 1.0 } |
| 113 |
} |
| 114 |
|
| 115 |
def __init__(self, matrix=BLOSUM62): |
| 116 |
self._matrix = matrix |
| 117 |
|
| 118 |
def score(self, x, y): |
| 119 |
try: |
| 120 |
return self._matrix[x][y] |
| 121 |
except KeyError as ke: |
| 122 |
raise ResidueNotFoundError(ke.message) |
| 123 |
|
| 124 |
@staticmethod |
| 125 |
def parse(string): |
| 126 |
""" |
| 127 |
Parse a standard scoring matrix file, where the first row and |
| 128 |
column are residue labels. |
| 129 |
|
| 130 |
@param string: scoring matrix string |
| 131 |
@type string: str |
| 132 |
|
| 133 |
@rtype: L{SimilarityMatrix} |
| 134 |
""" |
| 135 |
|
| 136 |
residues = {} |
| 137 |
matrix = {} |
| 138 |
|
| 139 |
for line in string.splitlines(): |
| 140 |
if not line.strip() or line.startswith("#"): |
| 141 |
continue |
| 142 |
|
| 143 |
if not residues: |
| 144 |
residues = line.split() |
| 145 |
|
| 146 |
else: |
| 147 |
items = line.split() |
| 148 |
if len(items) != len(residues) + 1: |
| 149 |
raise ValueError("{0} scoring columns expected".format(len(residues))) |
| 150 |
|
| 151 |
try: |
| 152 |
aa, scores = items[0], map(float, items[1:]) |
| 153 |
matrix[aa] = dict((residues[i], s) for i, s in enumerate(scores)) |
| 154 |
except (KeyError, ValueError): |
| 155 |
raise ValueError("Corrupt scoring matrix") |
| 156 |
|
| 157 |
return SimilarityMatrix(matrix) |
| 158 |
|
| 159 |
|
| 160 |
class AbstractAlignmentAlgorithm(object): |
| 161 |
""" |
| 162 |
Base class for all sequence alignment algorithms. |
| 163 |
|
| 164 |
This class was designed with simple sequence alignment algorithms in mind. |
| 165 |
Implementors have full control over the behavior of the scoring function and |
| 166 |
the dynamic programming matrix, but implementing things that require |
| 167 |
additional matrices (such as affine gap penalties) might be trickier. |
| 168 |
|
| 169 |
@param scoring: scoring matrix |
| 170 |
@type scoring: L{AbstractScoringMatrix} |
| 171 |
@param gap: simple gap penalty |
| 172 |
@type gap: float |
| 173 |
""" |
| 174 |
|
| 175 |
__metaclass__ = ABCMeta |
| 176 |
|
| 177 |
def __init__(self, scoring=IdentityMatrix(), gap=0): |
| 178 |
|
| 179 |
if not isinstance(scoring, AbstractScoringMatrix): |
| 180 |
raise TypeError(scoring) |
| 181 |
|
| 182 |
self._gap = float(gap) |
| 183 |
self._scoring = scoring |
| 184 |
|
| 185 |
@property |
| 186 |
def gap(self): |
| 187 |
""" |
| 188 |
Simple gap penalty |
| 189 |
@rtype: float |
| 190 |
""" |
| 191 |
return self._gap |
| 192 |
|
| 193 |
@property |
| 194 |
def scoring_matrix(self): |
| 195 |
""" |
| 196 |
Scoring matrix |
| 197 |
@rtype: L{AbstractScoringMatrix} |
| 198 |
""" |
| 199 |
return self._scoring |
| 200 |
|
| 201 |
def align(self, query, subject): |
| 202 |
""" |
| 203 |
Align two sequences and return the optimal alignment. |
| 204 |
|
| 205 |
@param query: first sequence |
| 206 |
@type query: L{AbstractSequence} |
| 207 |
@param subject: second sequence |
| 208 |
@type subject: L{AbstractSequence} |
| 209 |
|
| 210 |
@rtype: L{AlignmentResult} |
| 211 |
""" |
| 212 |
if query.length == 0 or subject.length == 0: |
| 213 |
raise ValueError("Can't align zero length sequence") |
| 214 |
|
| 215 |
# working with string sequences results in a massive speed-up |
| 216 |
qseq = ["*"] + self._sequence(query) |
| 217 |
sseq = ["*"] + self._sequence(subject) |
| 218 |
|
| 219 |
# 1. create a dynamic programming matrix |
| 220 |
matrix = [] |
| 221 |
rows, cols = len(query), len(subject) |
| 222 |
|
| 223 |
for i in range(rows + 1): |
| 224 |
matrix.append([]) |
| 225 |
for j in range(cols + 1): |
| 226 |
matrix[i].append(None) |
| 227 |
|
| 228 |
# 2. initialize the first row and column |
| 229 |
self._initialize(matrix) |
| 230 |
|
| 231 |
# fill |
| 232 |
for i in range(1, rows + 1): |
| 233 |
for j in range(1, cols + 1): |
| 234 |
score = self._score(qseq[i], sseq[j]) |
| 235 |
self._fill(matrix, i, j, score) |
| 236 |
|
| 237 |
# 3. compute alignment |
| 238 |
return self._traceback(matrix, query, subject) |
| 239 |
|
| 240 |
def _sequence(self, s): |
| 241 |
""" |
| 242 |
Extract and return the string sequence of {s}. |
| 243 |
|
| 244 |
@param s: sequence object |
| 245 |
@type s: L{AbstractSequence} |
| 246 |
|
| 247 |
@rtype: list of str |
| 248 |
""" |
| 249 |
return list(s.sequence) |
| 250 |
|
| 251 |
@abstractmethod |
| 252 |
def _initialize(self, matrix): |
| 253 |
""" |
| 254 |
Initialize (typically the first row and column) of the dynamic |
| 255 |
programming matrix. |
| 256 |
|
| 257 |
@param matrix: list (2D) |
| 258 |
@type matrix: list |
| 259 |
""" |
| 260 |
pass |
| 261 |
|
| 262 |
def _score(self, residue1, residue2): |
| 263 |
""" |
| 264 |
Retrieve the pairwise score of two residues using the current |
| 265 |
scoring matrix. |
| 266 |
|
| 267 |
@rtype: float |
| 268 |
""" |
| 269 |
return self._scoring.score(residue1, residue2) |
| 270 |
|
| 271 |
def _fill(self, matrix, i, j, score): |
| 272 |
""" |
| 273 |
Compute and set the best score that leads to cell i,j in the dynamic |
| 274 |
programming matrix: right, down or diagonal. |
| 275 |
|
| 276 |
See also L{AbstractAlignmentAlgorithm._max}. |
| 277 |
|
| 278 |
@param score: pairwise score at matrix[i][j] |
| 279 |
@type score: float |
| 280 |
@return: the best score |
| 281 |
@rtype: float |
| 282 |
""" |
| 283 |
|
| 284 |
match = matrix[i-1][j-1] + score |
| 285 |
insertion = matrix[i][j-1] + self._gap |
| 286 |
deletion = matrix[i-1][j] + self._gap |
| 287 |
|
| 288 |
best = self._max(match, insertion, deletion) |
| 289 |
matrix[i][j] = best |
| 290 |
|
| 291 |
return best |
| 292 |
|
| 293 |
@abstractmethod |
| 294 |
def _max(self, match, insertion, deletion): |
| 295 |
""" |
| 296 |
Choose the best score among all given possibilities: |
| 297 |
scores for match, insertion and deletion. This will determine |
| 298 |
the direction taken at each step while building the dynamic programming |
| 299 |
matrix (diagonal, down or right). |
| 300 |
|
| 301 |
This is an expected notable point of divergence for most sequence |
| 302 |
alignment algorithms. |
| 303 |
""" |
| 304 |
pass |
| 305 |
|
| 306 |
def _traceback(self, m, seq1, seq2): |
| 307 |
""" |
| 308 |
Trace back and return the optimal alignment. |
| 309 |
""" |
| 310 |
|
| 311 |
query = [] |
| 312 |
subject = [] |
| 313 |
|
| 314 |
# working with string sequences results in a massive speed-up |
| 315 |
qseq = ["*"] + self._sequence(seq1) |
| 316 |
sseq = ["*"] + self._sequence(seq2) |
| 317 |
|
| 318 |
i, j = self._terminus(m) |
| 319 |
qstart, start = i, j |
| 320 |
qend, end = i, j |
| 321 |
score = m[i][j] |
| 322 |
|
| 323 |
while self._expandable(m, i, j): |
| 324 |
|
| 325 |
if i > 0 and j > 0 and m[i][j] == (m[i-1][j-1] + self._score(qseq[i], sseq[j])): |
| 326 |
query.append(seq1.residues[i]) |
| 327 |
subject.append(seq2.residues[j]) |
| 328 |
qstart, start = i, j |
| 329 |
i, j = i - 1, j - 1 |
| 330 |
|
| 331 |
elif i > 0 and m[i][j] == (m[i-1][j] + self._gap): |
| 332 |
query.append(seq1.residues[i]) |
| 333 |
subject.append(ResidueInfo(-1, seq2.alphabet.GAP)) |
| 334 |
qstart = i |
| 335 |
i = i - 1 |
| 336 |
|
| 337 |
elif j > 0 and m[i][j] == (m[i][j-1] + self._gap): |
| 338 |
query.append(ResidueInfo(-1, seq1.alphabet.GAP)) |
| 339 |
subject.append(seq2.residues[j]) |
| 340 |
start = j |
| 341 |
j = j - 1 |
| 342 |
|
| 343 |
else: |
| 344 |
assert False |
| 345 |
|
| 346 |
query.reverse() |
| 347 |
subject.reverse() |
| 348 |
|
| 349 |
aligned_query = RichSequence(seq1.id, seq1.header, query, seq1.type) |
| 350 |
aligned_subject = RichSequence(seq2.id, seq2.header, subject, seq2.type) |
| 351 |
|
| 352 |
return AlignmentResult(score, aligned_query, aligned_subject, qstart, qend, start, end) |
| 353 |
|
| 354 |
@abstractmethod |
| 355 |
def _terminus(self, matrix): |
| 356 |
""" |
| 357 |
Find the coordinates of the optimal alignment's right endpoint in the |
| 358 |
dynamic programming matrix. This is the starting point of a traceback. |
| 359 |
|
| 360 |
@param matrix: the complete dynamic programming matrix |
| 361 |
@type matrix: 2D list |
| 362 |
|
| 363 |
@rtype: 2-tuple (i, j) |
| 364 |
""" |
| 365 |
pass |
| 366 |
|
| 367 |
@abstractmethod |
| 368 |
def _expandable(self, i, j): |
| 369 |
""" |
| 370 |
Return True if the traceback procedure must not terminate at |
| 371 |
position C{i,j} in the dynamic programming matrix. |
| 372 |
|
| 373 |
@rtype: bool |
| 374 |
""" |
| 375 |
pass |
| 376 |
|
| 377 |
|
| 378 |
class GlobalAlignmentAlgorithm(AbstractAlignmentAlgorithm): |
| 379 |
""" |
| 380 |
Needleman-Wunsch global sequence alignment. |
| 381 |
""" |
| 382 |
|
| 383 |
def __init__(self, scoring=IdentityMatrix(), gap=0): |
| 384 |
super(GlobalAlignmentAlgorithm, self).__init__(scoring, gap) |
| 385 |
|
| 386 |
def _initialize(self, matrix): |
| 387 |
|
| 388 |
for i in range(len(matrix)): |
| 389 |
matrix[i][0] = self._gap * i |
| 390 |
for j in range(len(matrix[0])): |
| 391 |
matrix[0][j] = self._gap * j |
| 392 |
|
| 393 |
def _max(self, match, insertion, deletion): |
| 394 |
return max(match, insertion, deletion) |
| 395 |
|
| 396 |
def _terminus(self, matrix): |
| 397 |
|
| 398 |
i = len(matrix) - 1 |
| 399 |
j = len(matrix[0]) - 1 |
| 400 |
|
| 401 |
return (i, j) |
| 402 |
|
| 403 |
def _expandable(self, matrix, i, j): |
| 404 |
return i > 0 or j > 0 |
| 405 |
|
| 406 |
class LocalAlignmentAlgorithm(AbstractAlignmentAlgorithm): |
| 407 |
""" |
| 408 |
Smith-Waterman local sequence alignment. |
| 409 |
""" |
| 410 |
|
| 411 |
START = 0 |
| 412 |
""" |
| 413 |
Score for initiation of a new local alignment |
| 414 |
""" |
| 415 |
|
| 416 |
def __init__(self, scoring=IdentityMatrix(), gap=-1): |
| 417 |
super(LocalAlignmentAlgorithm, self).__init__(scoring, gap) |
| 418 |
|
| 419 |
def _initialize(self, matrix): |
| 420 |
|
| 421 |
for i in range(len(matrix)): |
| 422 |
matrix[i][0] = LocalAlignmentAlgorithm.START |
| 423 |
for j in range(len(matrix[0])): |
| 424 |
matrix[0][j] = LocalAlignmentAlgorithm.START |
| 425 |
|
| 426 |
def _max(self, match, insertion, deletion): |
| 427 |
return max(match, insertion, deletion, LocalAlignmentAlgorithm.START) |
| 428 |
|
| 429 |
def _terminus(self, matrix): |
| 430 |
|
| 431 |
maxi, maxj = 0, 0 |
| 432 |
|
| 433 |
for i in range(len(matrix)): |
| 434 |
for j in range(len(matrix[i])): |
| 435 |
if matrix[i][j] > matrix[maxi][maxj]: |
| 436 |
maxi, maxj = i, j |
| 437 |
|
| 438 |
return (maxi, maxj) |
| 439 |
|
| 440 |
def _expandable(self, matrix, i, j): |
| 441 |
return matrix[i][j] != LocalAlignmentAlgorithm.START |
| 442 |
|
| 443 |
|
| 444 |
class AlignmentResult(object): |
| 445 |
""" |
| 446 |
Represents a pairwise sequence alignment result. |
| 447 |
|
| 448 |
@param score: raw alignment score |
| 449 |
@type score: float |
| 450 |
@param query: aligned query sequence (with gaps) |
| 451 |
@type query: L{AbstractSequence} |
| 452 |
@param subject: aligned subject sequence (with gaps) |
| 453 |
@type subject: L{AbstractSequence} |
| 454 |
@param qstart: query start position |
| 455 |
@type qstart: int |
| 456 |
@param qend: query end position |
| 457 |
@type qend: int |
| 458 |
@param start: subject start position |
| 459 |
@type start: int |
| 460 |
@param end: subject end position |
| 461 |
@type end: int |
| 462 |
""" |
| 463 |
|
| 464 |
def __init__(self, score, query, subject, qstart, qend, start, end): |
| 465 |
|
| 466 |
if not isinstance(query, AbstractSequence): |
| 467 |
raise TypeError(query) |
| 468 |
if not isinstance(subject, AbstractSequence): |
| 469 |
raise TypeError(query) |
| 470 |
|
| 471 |
if not (len(query) == len(subject)): |
| 472 |
raise ValueError("Corrupt alignment") |
| 473 |
|
| 474 |
self._score = float(score) |
| 475 |
self._query = query |
| 476 |
self._subject = subject |
| 477 |
self._qstart = int(qstart) |
| 478 |
self._qend = int(qend) |
| 479 |
self._start = int(start) |
| 480 |
self._end = int(end) |
| 481 |
self._identicals = 0 |
| 482 |
self._gaps = 0 |
| 483 |
self._length = 0 |
| 484 |
|
| 485 |
if query.length > 0 and subject.length > 0: |
| 486 |
|
| 487 |
if not 1 <= qstart <= qend: |
| 488 |
raise ValueError("Invalid query start/end positions") |
| 489 |
if not 1 <= start <= end: |
| 490 |
raise ValueError("Invalid subject start/end positions") |
| 491 |
|
| 492 |
qgap = query.alphabet.GAP |
| 493 |
sgap = subject.alphabet.GAP |
| 494 |
|
| 495 |
for q, s in zip(query, subject): |
| 496 |
if q.type == qgap or s.type == sgap: |
| 497 |
self._gaps += 1 |
| 498 |
elif q.type == s.type: |
| 499 |
self._identicals += 1 |
| 500 |
|
| 501 |
self._length = (self._gaps + (qend - qstart + 1) + (end - start + 1)) / 2 |
| 502 |
|
| 503 |
else: |
| 504 |
if (score + qstart + qend + start + end) != 0: |
| 505 |
raise ValueError("Corrupt alignment") |
| 506 |
self._length = 0 |
| 507 |
|
| 508 |
|
| 509 |
def __str__(self): |
| 510 |
string = "{0.qstart:5} {0.query.sequence:} {0.qend:<5}\n" |
| 511 |
string += "{0.start:5} {0.subject.sequence:} {0.end:<5}" |
| 512 |
return string.format(self) |
| 513 |
|
| 514 |
@property |
| 515 |
def is_empty(self): |
| 516 |
""" |
| 517 |
Return True if this is an empty alignment (i.e. no matches) |
| 518 |
@rtype: bool |
| 519 |
""" |
| 520 |
return self.length == 0 or self.gaps == self.length |
| 521 |
|
| 522 |
@property |
| 523 |
def score(self): |
| 524 |
""" |
| 525 |
Raw alignment score |
| 526 |
@rtype: float |
| 527 |
""" |
| 528 |
return self._score |
| 529 |
|
| 530 |
@property |
| 531 |
def query(self): |
| 532 |
""" |
| 533 |
Aligned query sequence (with gaps) |
| 534 |
@rtype: L{AbstractSequence} |
| 535 |
""" |
| 536 |
return self._query |
| 537 |
|
| 538 |
@property |
| 539 |
def subject(self): |
| 540 |
""" |
| 541 |
Aligned subject sequence (with gaps) |
| 542 |
@rtype: L{AbstractSequence} |
| 543 |
""" |
| 544 |
return self._subject |
| 545 |
|
| 546 |
@property |
| 547 |
def qstart(self): |
| 548 |
""" |
| 549 |
Query start position |
| 550 |
@rtype: int |
| 551 |
""" |
| 552 |
return self._qstart |
| 553 |
|
| 554 |
@property |
| 555 |
def qend(self): |
| 556 |
""" |
| 557 |
Query end position |
| 558 |
@rtype: int |
| 559 |
""" |
| 560 |
return self._qend |
| 561 |
|
| 562 |
@property |
| 563 |
def start(self): |
| 564 |
""" |
| 565 |
Subject start position |
| 566 |
@rtype: int |
| 567 |
""" |
| 568 |
return self._start |
| 569 |
|
| 570 |
@property |
| 571 |
def end(self): |
| 572 |
""" |
| 573 |
Subject end position |
| 574 |
@rtype: int |
| 575 |
""" |
| 576 |
return self._end |
| 577 |
|
| 578 |
@property |
| 579 |
def identicals(self): |
| 580 |
""" |
| 581 |
Number of identical residues |
| 582 |
@rtype: int |
| 583 |
""" |
| 584 |
return self._identicals |
| 585 |
|
| 586 |
@property |
| 587 |
def identity(self): |
| 588 |
""" |
| 589 |
Percentage of identical residues |
| 590 |
@rtype: int |
| 591 |
""" |
| 592 |
return float(self._identicals) / self._length |
| 593 |
|
| 594 |
@property |
| 595 |
def gaps(self): |
| 596 |
""" |
| 597 |
Total number of gaps (query + subject) |
| 598 |
@rtype: int |
| 599 |
""" |
| 600 |
return self._gaps |
| 601 |
|
| 602 |
@property |
| 603 |
def length(self): |
| 604 |
""" |
| 605 |
Alignment length (query + subject + gaps / 2) |
| 606 |
@rtype: int |
| 607 |
""" |
| 608 |
return self._length |
| 609 |
|
| 610 |
def alignment(self): |
| 611 |
""" |
| 612 |
@return: as a sequence alignment object |
| 613 |
@rtype: L{SequenceAlignment} |
| 614 |
""" |
| 615 |
return SequenceAlignment([self.query, self.subject]) |
| 616 |
|
| 617 |
|