Sequence Alignment Algorithm

Question

Algorithms

My regards!

There are four character sequences:

dbca,
AC
ACB
BCA

It is necessary to transform these sequences into (approximately) the following:

D-BCA-
-AC--
-ACB
--BCA-

That is, "align" these sequences in such a way that among all sequences in each position there is the maximum number of identical elements (clumsily in words; I hope it is clearer from the example).

Wikipedia on Sequence Alignment offers a number of algorithms, but they work with two sequences, while I need to align more and I can’t figure out how to extend them to process N sequences.

Maybe the collective mind has something to offer? There are no restrictions on memory and algorithmic complexity - sequences of at least 4 elements each, their total number is no more than 10.

Answer 1

For the algorithm for 2, we have 2 pointers (or indices) - where we are on the first line and where on the second. Here we will store n (or 10) pointers and do the same (that is, iterate over the selected character and shift the pointers when they match). It is clear that it is inconvenient to do this with an array, as for the case of 2 lines, so I would start a structure that stores pointers and put the answers not in an array, but in a map. If it's not clear, I can quickly write code - it's not difficult (C ++ or Java)

Answer 2

Google "multiple sequence alignment"