Задача A. Минимальное расстояние Левенштейна ≡

Условие

Дано N строк, состоящих из заглавных латинских букв (аминокислот). Требуется написать программу, определяющую пару строк с наименьшим расстоянием Левенштейна, включающего вставки, удаления и замены символов. Вес замены равен 2, вес вставки и удаления равен 1.

Формат входного файла

Во входном файле содержатся N строк.

Формат выходного файла

Выходной файл должен содержать три целых числа — два различных номера строк, расстояние между которыми наименьшее, и само расстояние. Строки нумеруются от 1 до N.

Ограничения

N = 25. Длина строк не превосходит 1000 символов. Если существует несколько решений, выведите c минимальным N, минимизировать сначала первый номер, потом второй. Например 1 10, а не 2 9.

Примеры тестов

D
PN
LAD
S
RA
NP
AS
A
GPW
EGA
AQ
KY
FKG
GA
N
GPVSLGGLP
YR
G
PEAGPMISK
KGNN
GG
GPWM
NS
AGP
TDQNGG

2 15 1

Задача B. Минимальное расстояние Левенштейна с частотами ≡

Условие

Дано N строк, состоящих из заглавных латинских букв (аминокислот). Требуется написать программу, определяющую пару строк с наименьшим расстоянием Левенштейна, включающего вставки, удаления и замены символов. Вес удаления/вставки принять равным частоте данной аминокислоты. Частоты округлять до 5-го дробного знака. Замена, соответственно, складывается из суммы частот двух аминокислот.

Формат входного файла

Во входном файле содержатся N строк.

Формат выходного файла

Выходной файл должен содержать три числа (два целых и одно дробное) — два различных номера строк, расстояние между которыми наименьшее, и само расстояние (округлить до 2 дробных знаков). Строки нумеруются от 1 до N.

Ограничения

N = 25. Длина строк не превосходит 1000 символов. Если существует несколько решений, выведите c минимальным N, минимизировать сначала номер, потом второй. Например 1 10, а не 2 9.

Примеры тестов

D
PN
LAD
S
RA
NP
AS
A
GPW
EGA
AQ
KY
FKG
GA
N
GPVSLGGLP
YR
G
PEAGPMISK
KGNN
GG
GPWM
NS
AGP
TDQNGG

5 8 0.03

Задача C. BLOSUM Scoring Matrices ≡

Условие

Дано N строк одинаковой длины L, состоящих из заглавных латинских букв (аминокислот). Требуется написать программу, вычисляющую BLOSUM Scoring Matrix для букв, встречающихся в заданном наборе строк.

Формат входных данных

Во входном файле содержатся N строк.

Формат выходных данных

Выходной файл должен содержать C строк, где C — это количество аминокислот (букв), встречающихся в строках.

i-я строка (нумерация с единицы) содержит i целых чисел — элементы BLOSUM матрицы. Вместо элементов матрицы, вычисление которых некорректно из-за отсутствия соответствующих пар во входных данных, требуется вывести 0.

Ограничения

N ≤ 5000

L ≤ 1000

Примеры тестов

ACD
DCE
BCE
BCD
ACB

2
3 -1
0 0 3
1 1 0 -1
0 1 0 3 2

AAI
SAL
TAL
TAV
AAL

2
0 0
0 4 3
0 0 0 0
0 0 0 4 2
0 4 4 0 0 0

Задача D. Выравнивание строк ≡

Условие

Вам даны:

• Числа D, E — штрафы за начало нового разрыва в выравнивании строк и штраф за его продолжение соответственно.

• Алфавит символов в виде строки A, состоящей из заглавных латинских букв.

• Матрица замен символов R, соответствующая стоимости сопоставления каждой пары символов при выравнивании строк. Строки и столбцы матрицы соответствуют символам алфавита в том порядке, в котором они указаны в строке A

• Две строки P и Q.

Требуется найти выравнивание строк P и Q, максимизирующее функцию стоимости данного выравнивания.

Выравнивание двух строк это также пара строк (Q₁, Q₂) одинаковой длины L, состоящих из символов алфавита, и символа "-", означающего разрыв.

Стоимость выравнивания S вычисляется по формуле: S(Q₁, Q₂) = ∑L − 1i = 0f(Q₁[i], Q₂[i]),

где f(Q₁[i], Q₂[i]) = D, если выполнено хотя бы одно из условий

• Q₁[i] равен "-", а Q₁[i − 1] не равен "-"
• Q₂[i] равен "-", а Q₂[i − 1] не равен "-"

f(Q₁[i], Q₂[i]) = E, если выполнено хотя бы одно из условий

• Q₁[i] равен "-", и Q₁[i − 1] равен "-"
• Q₂[i] равен "-", и Q₂[i − 1] равен "-"

Иначе f(Q₁[i], Q₂[i]) = R[Q₁[i]][Q₂[i]]

Формат входных данных

Первая строка содержит целые числа D, E.

Вторая строка содержит строку-алфавит A.

Далее |A| строк содержат по |A| целых чисел — элементы матрицы R.

Последние две строки содержат строки P и Q.

Формат выходных данных

В первой строке выходного файла выведите стоимость выравнивания.

В последующих двух строках выведите выравнивание.

Если оптимальных решений несколько, выведите любое из них.

Ограничения

|D, E| ≤ 1000

 − 10 ≤ R_ij ≤ 10

Длина строк не превосходит 500. Строки состоят только из символов алфавита и не могут быть пустыми.

Примеры тестов

-5 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT

-4
GAAAAAAT
G----AAT

0 -1
AGCT
1 -1 -1 -1 
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 1
GAAAAAAT
GAAT

3
GAAAAAAT
G-A-A--T

-4 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT

20
--AGACTAGTTAC
CGAGAC--G-T--

-18 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT

-10
AGACTAGTTAC
---CGAGACGT

Задача G. Оценка параметров HMM ≡

Условие

Дано C строк, где последняя является нуклеотидной последовательностью длины L с CpG островками, а остальные содержат координаты островков в последовательности. Требуется написать программу, расcчитывающую по этим данным начальные и переходные вероятности для 8 состояний — 4 нуклеотида c "-" или "+" состояниями. "+" соответствует нуклеотидам в CpG островке. Псевдокаунт в числителе для каждого состояния принять равным 10^− 30, в знаменателе — 1. То есть переходная вероятность для С+G+ будет a_{C + G +} = C_{C + G +} + 10^− 30C_C + N + 1.

A начальная вероятность для G- будет a_{0 G −} = C_G − + 10^− 30C_N − + 1.

Где N −  ∈ {A − , C − , G − , T − } и N ∈ {A − , C − , G − , T − , A + , C + , G + , T + }.

Формат входного файла

Во входном файле содержатся C строк. Последняя содержит нуклеотидную последовательность длины L, а первые C − 1 строк содержат координаты CpG островков. Отсчет идет с 1, координаты включают первый и последний символ островка.

Формат выходных данных

Выходной файл должен содержать 68 строк, сначала начальные вероятности для каждого state, где state ∈ {A − , C − , G − , T − }, затем переходные вероятности для каждого state 1 − state 2, где state ∈ {A − , C − , G − , T − , A + , C + , G + , T + }. Порядок вывода вероятности лексиграфический, в соответствии с порядком в state.

При расчетах вероятности выражаем в натуральном логарифме и округляем до 5-го знака после запятой.

Ограничения

C < 12

L < 100000.

Примеры тестов

3 26
ATCGCGCGCGCGCGCGCGCGCGCGCG

-1.09861
-70.17617
-70.17617
-1.09861
-69.7707
-69.7707
-69.7707
-0.69315
-69.7707
-69.7707
-69.7707
-69.7707
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.7707
-69.7707
-69.7707
-69.7707
-69.7707
-0.69315
-69.7707
-69.7707
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-71.6425
-71.6425
-71.6425
-71.6425
-71.6425
-71.6425
-0.08004
-71.6425
-71.56246
-71.56246
-71.56246
-71.56246
-71.56246
-0.08701
-71.56246
-71.56246
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755

Задача H. Поиск CpG островков с помощью HMM ≡

Условие

Дано N строк, где последняя является нуклеотидной последовательностью длины L с CpG островками, а остальные содержат начальные и переходные вероятности для HMM. Эмиссионные вероятности считать равными log(10^− 30) или log(1) в зависимости от соответствия состояния наблюдаемому нуклеотиду. Требуется написать программу, находящую координаты CpG островков в соответствии с заданной HMM с помощью алгоритма Витерби.

Формат входного файла

Во входном файле содержатся N строк, где последняя содержит нуклеотидную последовательность длиной L с CpG островками, а остальные N − 1 строк содержат начальные и переходные вероятности.

Формат выходных данных

Выходной файл должен содержать координаты CpG островков, за начало отчета принять 1. Значения координат соответствуют первому и последнему символу островка.

Ограничения

C = 73

L < 100000.

Примеры тестов

A- -1.5432280925
C- -1.2610374051
G- -1.3076859937
T- -1.4589003294
A+ -80.3306836858
C+ -80.3306836858
G+ -80.3306836858
T+ -80.3306836858
A- A- -1.3887851737
A- C- -1.4892913109
A- G- -1.0716151683
A- T- -1.702929469
A- A+ -78.7875162711
A- C+ -7.7640533322
A- G+ -78.7875162711
A- T+ -78.7875162711
C- A- -1.3249755321
C- C- -1.0620420215
C- G- -2.2855263362
C- T- -1.250203786
C- A+ -79.06969204
C- C+ -8.3827013377
C- G+ -79.06969204
C- T+ -79.06969204
G- A- -1.5733254273
G- C- -1.3248409469
G- G- -1.0813114769
G- T- -1.6749677516
G- A+ -79.0230456365
G- C+ -8.1537333775
G- G+ -79.0230456365
G- T+ -79.0230456365
T- A- -2.082681587
T- C- -1.2714529969
T- G- -1.1105065043
T- T- -1.3264377255
T- A+ -78.8717833564
T- C+ -9.101083386
T- G+ -78.8717833564
T- T+ -78.8717833564
A+ A- -76.1898802345
A+ C- -76.1898802345
A+ G- -76.1898802345
A+ T- -76.1898802345
A+ A+ -1.7991214657
A+ C+ -1.1461807056
A+ G+ -0.9199649552
A+ T+ -2.1425141451
C+ A- -77.0184925521
C+ C- -77.0184925521
C+ G- -77.0184925521
C+ T- -77.0184925521
C+ A+ -1.6419905155
C+ C+ -0.9939637702
C+ G+ -1.4306814218
C+ T+ -1.6255817608
G+ A- -7.139660336
G+ C- -5.8868973675
G+ G- -5.6355829392
G+ T- -7.139660336
G+ A+ -1.8589979047
G+ C+ -1.0700780096
G+ G+ -1.0946550219
G+ T+ -1.8438460996
T+ A- -76.2667205282
T+ C- -76.2667205282
T+ G- -76.2667205282
T+ T- -76.2667205282
T+ A+ -2.7348204422
T+ C+ -0.9866322212
T+ G+ -0.9430609729
T+ T+ -1.7598221095
ATCGCGCGCGCGCGCGCGCGCGCGCG

3 26

Задача I. Моделирование вторичной структуры РНК ≡

Условие

Дана нуклеотидная последовательность РНК длины L. Требуется написать программу, моделирующую вторичную структуру РНК с помощью алгоритма Нуссинов (при обратном проходе последовательность возможных ходов по матрице не менять местами! См. стр. 13 из 4-й лекции). Длина петель должна быть не менее 3 нуклеотидов, при ветвлении между шпильками должно быть не менее 2 нуклеотидов. Учитывать лишь Уотсон-Криковские пары G-C, A-T и обратные им.

Формат входного файла

Во входном файле содержится одна строка.

Формат выходных данных

Выходной файл должен содержать число комплементарных пар нуклеотидов, образующих шпильки и саму структуру, где спаренные нуклеотиды обозначены знаком  <  или  > , а неспаренные точками. Например последовательность GGGAAAATCC будет записана как . <  <  < ... >  >  > .

Ограничения

L < 100.

Примеры тестов

GGGAAAAUCC

3 .>>>...<<<

GGGAAAAUCCCCUAUGCGAUAA

6 .>>>...<<<..>>>...<<<.

GGAAAAUCCCCUAUGCGAUAAAAAAGCGUUU

9 >>>...<<<..>>>...<<<..>>>...<<<

Задача J. Сборка генома SARS-CoV2 ≡

Условие

Даны N нуклеотидных последовательностей ридов длиной L, полученных с участков генома коронавируса SARS-CoV2. Требуется написать программу, создающую граф де Брюйна, проверяющую наличие эйлерова пути и строящую по этому пути искомую нуклеотидную последовательность (геном). Кратными ребрами (мультиграф) пренебрегаем, то есть считаем за одно, если направление ребер одинаковое. Между альтернативными ребрами выбирается лексиграфически наименьшее. Длина вершины/узла графа должна быть равна 30 нуклеотидам, а ребро — 31. Количество вершин в графе обычно не более количества ридов.

Формат входного файла

Входной файл имеет формат FASTA и содержит L ридов.

Формат выходных данных

Выходной файл должен содержать одну нуклеотидную последовательность (геном), если есть эйлеров путь по графу, иначе None

Ограничения

N < 4000

L ≤ 100.

Примеры тестов

>simulated.1
CACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATGAAGGTAATT
>simulated.2
ATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGA
>simulated.3
ATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTAT
>simulated.4
ATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGC
>simulated.5
TGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGAC
>simulated.6
GACATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGC
>simulated.7
TCTTACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTG
>simulated.8
TACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATG
>simulated.9
GTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCT
>simulated.10
ATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGCTT

GACATGGTACCACATATATCACGTCAACGTCTTACTAAATACACAATGGCAGACCTCGTCTATGCTTTAAGGCATTTTGATGAAGGTAATT