4
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is almost what I need. However, DHD is valid only for sequences of equal length. $\endgroup$ – curryage Sep 24 '15 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$ – Gilbert Sep 24 '15 at 10:44
  • $\begingroup$ Indeed. Nice, insightful answer ! $\endgroup$ – curryage Sep 25 '15 at 7:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.