This is a test version of Biostars. For the public version, visit https://www.biostars.org.
What to use for a measure of distance between two sequences?

I've got a lot of genetic sequences and I'd like to use various clustering algorithms on them, but this requires a measure of the distance between two sequences. I've used BLAST+ and the Needleman-Wunsch algorithm, but both give measures of similarity rather than distance (i.e. two similar sequences have a large similarity score, and a low distance). I've found methods for whole genomes, but here I just want it for pairs of genes.

Is there a good way to get distance from similarity score? Ideally I'd like something where two identical sequences have a distance of zero and distance from sequence A to sequence B is the same as B to A.

Or is there some other method that finds a distance directly from the sequences (without first computing similarity)?

There's a variety of ways I can think of combining similarity scores to give something a bit like a distance (e.g. D(A, B) = 1 / similarity(A, B), or D(A, B) = min(sim(A,A), sim(B,B)) / sim(A,B) - 1) but I'm sure someone must have done this before and have a better solution! All help greatly appreciated.

alignment blast genetic-distance
• 9,313 views • link
updated by Ram Ram • written by evsmithx • evsmithx

2 answers

A popular distance metric is the Levenshtein distance. There's a python package for it and I guess you could use it as follows to compute the distance between pairs of strings:

import Levenshtein as lv
1 - lv.ratio('ACTG', 'ACTA')
>>> 0.25

Just a thought...

• 0 views • link
updated by Ram Ram • written by dariober dariober

I think that conventional way of thinking about the correlation between similarity and distance is the following:

Distance = 1 - Similarity
• 0 views • link
updated by Ram Ram • written by Gergana Vandova Gergana Vandova

Log in to answer this question.

More posts like this