Множественное выравнивание последовательностей для общих строк java

Question

Я работаю в hadoop, и я должен выровнять n строк в java, и мне нужен алгоритм, который вычисляет общие строки (без биоинформатики, генома и т. Д.) В Java. Es.

ASFHASFHASDSAAPJEIHRA <-- seq1 
AAPSOFHASFDSOISISN--A <-- seq2 
AWP-JWRAIADSDIA--N--A <-- seq3 
AOPSJD-A-JDSSDSOQOSSJ <-- seq4 
100000000011000000000 <-- score 

Кто-то может помочь мне в названии, библиотеке или что-то еще?

Answer 1

Вы можете написать свой собственный алгоритм динамического программирования, но сложность: O (N^k), если N - длина последовательности и k - количество последовательностей. Предположим, что у вас есть k = 2 последовательности: У вас есть 2D сетка, где каждая точка в вашей сетке соответствует паре символов. Таким образом, положение (1,1) соответствует слову 1 [1] и слову2 [1]. Горизонтальные и вертикальные края в этой сетке соответствуют вставкам и удалениям, а диагональные - совпадениям или несоответствиям. Для каждого из них вы должны наложить штраф. В вашем примере match = +1, а остальные возможности - +0. Когда вы достигаете нижнего правого края сетки, вы получаете оптимальный балл выравнивания.