# Are there any algorithms or researches on finding local alignments in partially ordered sequences?

The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of information on that.

However, recently, I had to tackle a problem in which sequences had partial orders - meaning that some parts of the sequences (if you can even call it that) was not imposed a strict restriction of ordering.

For example, we could have a protein sequence of GAC(AG)TT, where the brackets denote that any elements within them can be freely reordered. Hence, the sequence can be viewed as either GACAGTT or GACGATT.

A naive way to approach the problem is to compare all possible configurations of sequences, but the problem size becomes exponentially larger as the number of brackets (clusters of freely interchangeable elements) and the numbers of elements in each bracket increase.

I have tried looking up in algorithm textbooks, googling in general webpages and publications, but I could not find the slightest hint of such problem. It seems very peculiar (or very unlikely) that such a general problem has not been mentioned anywhere until now. So please, could anyone here shed some light on my question? Thank you.

• How long can these bracketed subsequences be? – Raphael Jul 15 '15 at 5:51
• @Raphael It could vary, but the maximum length of such bracketed subsequences is around 20. I seemed to have omitted the general statistics of the data, so here are some more numbers: the sequences are usually 500 long, and the entire sequences are usually full of brackets - there are rarely any brackets with only one element. – Kang Min Yoo Jul 15 '15 at 6:57
• I guess alignment is usually based on minimizing some edit distance between strings, such as, for example, Levenshtein distance. It is characterized by a set of change operations that can be applied to one string to get the other, and possibly weights assigned to each change operation. You want to extend the concept to other, non linear structures. Before you worry about an algorithm, you should first define what is acceptable as an alignment, and why. For example, can you align GAC(AG)TT and GA(CA)GTT, and what does it mean. Short of that, looking for an algoritm is waste of time. – babou Jul 15 '15 at 13:28