Выравнивание нескольких (небиологических, дискретных состояний) последовательностей - PullRequest
Новая
       9

Выравнивание нескольких (небиологических, дискретных состояний) последовательностей

2 голосов
/ 20 апреля 2019

У меня есть некоторые данные, которые описывают упорядоченный набор дискретных событий (или состояний).Существует 34 возможных состояния, которые могут встречаться в любом порядке и могут повторяться.Каждая последовательность событий может содержать любое количество событий, и, что особенно важно, существует более 2 последовательностей событий.Моя конечная цель - объединить эти последовательности в похожие подмножества, но я догадываюсь, что это не может быть значимым, если эти последовательности не выровнены так, чтобы эквивалентные события занимали одинаковое положение во всех последовательностях.

Я очень хорошо знаком смножественное выравнивание биологических последовательностей, но все программное обеспечение, с которым я сталкивался для этого (MUSCLE, MAFFT, T-COFFEE, Clustal * и т. д.), требует последовательности ДНК, РНК или АА, и у меня больше состояний, чем у любого из них, поэтомуЯ не могу заставить их работать.

Я нашел различные реализации алгоритмов выравнивания попарно , такие как Needleman-Wunsch в R, но до сих пор не встречал каких-либо общих(небиологические) реализации любых множественных алгоритмов выравнивания последовательностей.

Например, скажем, мои данные выглядят так: 

1: ABCDEFG
2: ACDGH
3: BDEFEGI
4: AH
5: DEGHI

Моя цель - получить ихвыглядеть следующим образом: 

1: ABCDEF-G--
2: A-CD---GH-
3: -B-DEFE--I
4: A-------H-
5: ---DE--GHI

Где символ - обозначает отсутствие события в этой последовательности.Это упрощенный пример, на самом деле я ищу что-то, что штрафует за открытие пробелов (-) так же, как это делают алгоритмы MSA с биологической последовательностью.

Единственное программное обеспечение, которое у меня естьобнаружил, что, возможно, это возможно, это Alphamalig (http://alggen.lsi.upc.es/recerca/align/alphamalig/intro-alphamalig.html), но он старый, и я не могу заставить его работать на моей машине. В идеале я хотел бы что-то, что может быть реализовано в R.

Ответы [ 2 ]

2 голосов
/ 20 апреля 2019

Предполагая, что нам нужно сопоставить с LETTERS, можно выбрать str_match, затем изменить NA на -, paste

library(stringr)
library(dplyr)
f1 <- Vectorize(function(x) str_match(x, LETTERS))
out1 <- f1(v1)
do.call(paste0, as.data.frame(t(replace_na(out1[!!rowSums(!is.na(out1)),], '-'))))
#[1] "ABCDEFG--" "A-CD--GH-" "-B-DEFG-I" "A------H-" "---DE-GHI"

Это также можно сделать с помощью match после разделения 

lst <- strsplit(v1, "")
mx <- match(max(sapply(lst, tail, 1)), LETTERS)
sapply(lst, function(x) paste(replace_na(x[match(LETTERS[seq_len(mx)], 
           x)], '-'), collapse=""))

Данные 

v1 <- c("ABCDEFG", "ACDGH", "BDEFEGI", "AH", "DEGHI")
1 голос
/ 24 апреля 2019

Я бы посоветовал использовать MAFFT выравнивание последовательности .Обычно это используется для выравнивания биологических последовательностей, но у него есть опция для выравнивания текста с использованием --anysymbol.Обратите внимание, что MAFFT является bash-скриптом и требует файл ввода / вывода.

входной файл (mafft_anysymbol_input.txt): 

>Seq1
ABCDEFG
>Seq2
ACDGH
>Seq3
BDEFEGI
>Seq4
AH
>Seq5
DEGHI

R код для запуска bash-скрипта: 

#Be sure that input/output and R files share the same path, otherwise you'll have to specify the path in the mafft script call.
x <- 'mafft --anysymbol mafft_anysymbol_input.txt > mafft_anysymbol_output.txt'
system(x)

Содержимое выходного файла (mafft_anysymbol_output.txt): 

>Seq1
ABCDEFG--
>Seq2
-ACDGH---
>Seq3
--BDEFEGI
>Seq4
----AH---
>Seq5
---DEGHI-

Редактировать - теперь я вижу, что вы знакомы с инструментами биологического выравнивания.Если вы хотите создать собственную матрицу оценок для выравнивания текста, проверьте параметры mafft - text и --textmatrix .Требуется ввод кода ascii (дополнительные преобразования типов данных), но у вас будет возможность связать похожие буквы (однако вы определите похожие) по количеству баллов.Например, вы можете связать прописные и строчные буквы или буквы с / без знаков ударения.

...