Алгоритм выравнивания числовых последовательностей

Привет. У меня есть две последовательности числовых данных, скажем:
S1: 1,6,4,9,8,7,5 и S2: 6,9,7,5 < br> И я хотел бы найти выравнивание последовательностей как в смысле слева-направо, так и справа-слева.
Итак, я использовал 2 метода, прежде чем спросить, я действительно использовал венгерский алгоритм, но он не последовательный, поэтому он не дает хороших результатов результаты
И я использовал модифицированную версию алгоритма Нидлмана – Вунша, но я думаю, что я, возможно, делаю это неправильно или что-то в этом роде, и я копал как минимум 4 месяца в поисках чего-либо, что могло бы мне помочь, но я нахожу только генетические алгоритмы, которые могут быть полезны, но мне было интересно, существует ли алгоритм, который я, возможно, еще не видел?
Итак, чтобы формализовать свой вопрос: Как бы вы выровняли два положительных числовых (целые или двойные) последовательности?


algorithm sequence-alignment
person Chakib Mataoui    schedule 14.05.2017    source источник
comment
Каким будет ожидаемый результат для двух последовательностей, показанных в вашем вопросе? И каково объяснение того, как вы получили такой результат?   -  person Bernhard Barker    schedule 15.05.2017
comment
Разве вам не следует попытаться выяснить, что не так с кодом, который вы написали до сих пор (путем отладки), вместо того, чтобы отбрасывать его и просить другого подхода?   -  person Bernhard Barker    schedule 15.05.2017
comment
@Dukeling, скажем, это будет массив, в котором у нас будут элементы, которые соответствуют лучшему (не настоящее идеальное совпадение), но, по крайней мере, самые близкие возможные элементы, поэтому этот пример является случайным и дает идеальное совпадение, например ([2 , 1], [4,2], [6,3], [7,4]) левый элемент является индексом последовательности S1, совпадающей с правым элементом, который является индексом S2, от которого я мог бы вычислить расстояние между этими двумя последовательностями, которые на самом деле были бы суммой несовпадающих элементов + суммой абсолютного вычитания согласованных элементов   -  person Chakib Mataoui    schedule 15.05.2017
comment
@Dukeling, я бы не стал просить другого подхода, если бы я не оценивал метод, который не работает неправильно, сэр, но я не тот, кто предлагал его использовать, и я очень много работал, чтобы найти другой подход, который я не мог найти, поэтому я надеюсь найти людей со знаниями, к которым у меня не было доступа, возможно, помогая даже давая мне просто подсказку, чтобы я мог продолжить и найти решение   -  person Chakib Mataoui    schedule 15.05.2017
comment
Это очень похоже на самую длинную распространенную проблему подпоследовательности. Вам нужно будет конкретно и точно определить, как вы будете сравнивать неточные совпадения, чтобы определить лучшее, если вам нужна помощь с этой частью.   -  person Bernhard Barker    schedule 15.05.2017
comment
Большое спасибо @Dukeling, но я действительно знаю, с какой проблемой я имею дело, единственное, что решения для самой длинной общей подпоследовательности сделаны для строк и используются, в частности, в генетических алгоритмах, но как насчет других данных какие в моем случае числа, вы хоть представляете?   -  person Chakib Mataoui    schedule 15.05.2017
comment
@Chekbo числа не проблема. Строки - это последовательности символов, вы имеете дело с числовыми последовательностями. Важно только то, совпадают ли два значения или нет. Или у вас проблемы с точностью? Тогда вы могли бы допустить небольшую относительную ошибку, чтобы два числа по-прежнему считались одинаковыми.   -  person maraca    schedule 15.05.2017
comment
@maraca, спасибо, но числа могут быть десятичными значениями. Я обобщил проблему, чтобы найти альтернативу на практике. Я использую это для вычисления расстояния между двумя последовательностями областей частей формы, и мне нужно это расстояние между ними, когда есть не одинаковое количество деталей между ними   -  person Chakib Mataoui    schedule 15.05.2017

Ответы (1)


arrow_upward
0
arrow_downward

Я считаю, что вы можете достичь своей цели следующим образом:

import string
from Bio import pairwise2
from Bio.pairwise2 import format_alignment

seq1 = "1649875"
seq2 = "6975"

numDict = {}
for x in range(0,10):
    for y in range(0,10):
        numDict[(str(x),str(y))] = -abs(x-y)
#print(numDict)

for a in pairwise2.align.globalds(seq1, seq2, numDict, -3, -1):
    print(format_alignment(*a)) #prints alignment with best score

#for a in pairwise2.align.globalms(seq1, seq2, 5, -5, -3, -1):
    print(format_alignment(*a))

Выравнивание globalds позволяет вам использовать собственный словарь (в этом случае я создал словарь, содержащий числа от 1 до 9, и нашел абсолютное значение их разницы в паре). Если вам просто нужна плоская система подсчета очков «да / нет», вы можете сделать что-то вроде globalms, где успех равен +5, а неудача --5. Обратите внимание, я советую использовать штрафы за пропуск при выполнении выравнивания. Также ознакомьтесь с «глобальными» и «локальными» согласованиями. Дополнительную информацию о модуле биопайтона Pairwise2 можно найти здесь: http://biopython.org/DIST/docs/api/Bio.pairwise2-module.html

person Ghoti    schedule 04.08.2017
comment
Спасибо за ваш ответ, но я действительно искал выравнивание, даже если числа разные, потому что последовательность на самом деле является последовательностью с плавающей запятой, но мне нужно более глобальное решение, и я действительно нашел его, я просто забыл поделиться им, поэтому я использовал Алгоритм Вунша Нидлмана, который я адаптировал к моей конкретной проблеме и для сравнения на самом деле data я просто сделал это естественно с абсолютными значениями и пробелом max (seq) + 1, я не знаю, почему +1 это сработало для меня, мне придется искать дальше, как это улучшить. - person Chakib Mataoui; 05.08.2017