[R] how to group a large list of strings into categories based on string similarity?

[G FANG]

Hi,

I want to group a large list (20 million) of strings into categories
based on string similarity?

The specific problem is: given a list of DNA sequence as below

ACTCCCGCCGTTCGCGCGCAGCATGATCCTG
ACTCCCGCCGTTCGCGCGCNNNNNNNNNNNN
CAGGATCATGCTGCGCGCGAACGGCGGGAGT
CAGGATCATGCTGCGCGCGAANNNNNNNNNN
CAGGATCATGCTGCGCGCGNNNNNNNNNNNN
......
.....
NNNNNNNCCGTTCGCGCGCAGCATGATCCTG
NNNNNNNNNNNNCGCGCGCAGCATGATCCTG
NNNNNNNNNNNNGCGCGCGAACGGCGGGAGT
NNNNNNNNNNNNNNCGCGCAGCATGATCCTG
NNNNNNNNNNNTGCGCGCGAACGGCGGGAGT
NNNNNNNNNNTTCGCGCGCAGCATGATCCTG

'N' is the missing letter

It can be seen that some strings are the same except for those N's
(i.e. N can match with any base)

given this list of string, I want to have

1) a vector corresponding to each row (string), for each string assign
an id, such that similar strings (those only differ at N's) have the
same id
2) also get a mapping list from unique strings ('unique' in term of
the same similarity defined above) to the ids

I am a matlab user shifting to R. Please advice on efficient ways to do this.

Thanks!

Gang