Edit distance between microRNAs

Question

[Richard]

Hi all,

Has anyone calculated the edit distance between microRNAs? We want to know how many base changes there are between the microRNAs in miRBase.

I was about to align them all to each other (not sure which tools is the best for something like this), but thought I'd ask to see if there is already an answer.

thanks!

Answer 1

[dariober]

What about something on these lines using python and the Levenshtein module: (not tested)

import Levenshtein as ls
import itertools

mirna= ['ACTG', 'ACG', 'TTTT']

# Get edit distance and ratio between all the pairs of miRNA:
for x, y in itertools.combinations(mirna, 2):
    print(x, y, ls.distance(x, y), ls.ratio(x, y))

Output:

('ACTG', 'ACG', 1, 0.8571428571428571)
('ACTG', 'TTTT', 3, 0.25)
('ACG', 'TTTT', 4, 0.0)

EDIT: Use itertools to generate pairs of miRNA.

Answer 2

[mikhail.shugay]

You can generate a blast database and align align all mirna sequences against it in a second pass. The choose some criteria for cutoff (e.g. top X hits with E-value > Y) and build lists of homologs for each mirna sequence. Then I would recommend building a cytoscape graph. It should be very easy, just input graph as "mir1\tmir2" and edge characteristics as "mir1 (pp) mir2\t2\t1" with header "interaction\tmismatches\tindels", push it to cytoscape and visualize using edge weights. The resulting picture should be awesome :)

[dariober]

However, the OP asks for edit distance between miRNAs. Blast would give the edit distance between best local alignments which might or might not be what it is asked.

[Richard]

Upvote for using "awesome" in the suggestion. Sounds good to me.

Answer 3

[Chirag Nepal]

If I understood the question properly, you could probably use closestBed while ignoring the same overlapping ones

closestBed -a mirbase.bed -b mirbase.bed -io

-io option removes overlapping ones, and there are other options available that u can play with.

BTW, what did you mean by edit distance (I mean in biological term)?

[Devon Ryan]

closestBed will find the closest feature in terms of physical proximity, which isn't what Richard is after. In short, an edit distance is a metric for comparing similarity.