Many sequence alignment algorithms and those which measure similarity between sequences require specification of a cost matrix defined on the sequence alphabet. However, the cost incurred does not take position into account. Are there algorithms which take position in the sequence into account ? A generic entry in the cost matrix for such an algorithm would be of the form $Cost(P,Q,i)$ which specifies the cost for replacing $P$ in the $i$-th position of the string with $Q$.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The seqdist function of the TraMineR R package proposes a DHD (Dynamic Hamming Distance) edit method that computes dissimilarities using position dependent costs. Costs can be provided as a 3-dimensional matrix with the third dimension being the position. By default they are derived from the transition probabilities as proposed by Laurent Lesnard (2006)
Lesnard, L. (2006). Optimal Matching and Social Sciences. Série des Documents de Travail du CREST, Institut National de la Statistique et des Etudes Economiques, 2006-01, Paris.
-
$\begingroup$ This is almost what I need. However, DHD is valid only for sequences of equal length. $\endgroup$– curryageCommented Sep 24, 2015 at 10:22
-
1$\begingroup$ Indeed. In optimal matching, the order in which indels and substitutions are performed is arbitrary, and so the position at which substitutions are done is arbitrary. Which position would you then chose? $\endgroup$– GilbertCommented Sep 24, 2015 at 10:44
-
$\begingroup$ Indeed. Nice, insightful answer ! $\endgroup$– curryageCommented Sep 25, 2015 at 7:58
$\begingroup$
$\endgroup$
Defining the matrix itself is simple and has been done so in the context of sequence matching for bioinformatics problems. It goes by the name Position Weight Matrix.
To actually utilize the matrix in a similarity measure, the dynamic programming formulation typically employed may need to be modified. No ready-to-use code seems to be available.