CODEWITHSUNDEEP
algorithm
Andrey Shchekin
Andrey Shchekin

Reputation: 21619

An algorithm for aggregation of similar sequences

Let's say you have a list of similar sequences, such as

a a a a
a b a a a
x a a a a y
...

You want to detect a common aggregate of all these sequences, such as

x? a b? a a a y?

where operator ? specifies that element is optional.

What algorithm would you use?

Upvotes: 4

Views: 205

Answers (3)

Alos
Alos

Reputation: 2715

You might want to check out smith-Waterman algorithm that is used for performing sequence alignments.

Upvotes: 1

Tobu
Tobu

Reputation: 25446

Look at the sequence alignment algorithms used in bioinformatics.

More specifically, since you have a list, multiple sequence alignment. The Viterbi algorithm should do.

Upvotes: 3

Gaim
Gaim

Reputation: 6844

I think that if you convert your list to suffix tree then it will be very simple recursive solution but I am not sure about asymptotic complexity

Upvotes: 1

Related Questions