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

Автор:Бойко   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:10 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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. Минимальное расстояние Левенштейна с частотами

Автор:Бойко   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:10 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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

Автор:М. Спорышев   Ограничение времени:8 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

N ≤ 5000

L ≤ 1000

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

Стандартный вход Стандартный выход
1
ACD
DCE
BCE
BCD
ACB
2
3 -1
0 0 3
1 1 0 -1
0 1 0 3 2
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. Выравнивание строк

Автор:М. Спорышев   Ограничение времени:10 сек
Входной файл:Стандартный вход   Ограничение памяти:1024 Мб
Выходной файл:Стандартный выход  

Условие

Вам даны:

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

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

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

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

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

Иначе f(Q1[i], Q2[i]) = R[Q1[i]][Q2[i]]

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

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

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

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

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

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

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

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

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

Ограничения

|D, E| ≤ 1000

 − 10 ≤ Rij ≤ 10

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

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

Стандартный вход Стандартный выход
1
-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
2
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
3
-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--
4
-18 -5
AGCT
10 -1 -3 -4
-1 7 -5 -3
-3 -5 9 0
-4 -3 0 8
AGACTAGTTAC
CGAGACGT
-10
AGACTAGTTAC
---CGAGACGT

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

Автор:Бойко   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:150 Мб
Выходной файл:Стандартный выход  

Условие

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

A начальная вероятность для G- будет a0G −  = CG −  + 10 − 30CN −  + 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 − }, затем переходные вероятности для каждого state1 − state2, где state ∈ {A − , C − , G − , T − , A + , C + , G + , T + }. Порядок вывода вероятности лексиграфический, в соответствии с порядком в state.

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

Ограничения

C < 12

L < 100000.

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

Входной файл (input.txt) Стандартный выход
1
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

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

Автор:Бойко   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:100 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

Ограничения

C = 73

L < 100000.

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

Входной файл (input.txt) Стандартный выход
1
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

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

Автор:Бойко   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Ограничения

L < 100.

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

Входной файл (input.txt) Стандартный выход
1
GGGAAAAUCC
3 .>>>...<<<
2
GGGAAAAUCCCCUAUGCGAUAA
6 .>>>...<<<..>>>...<<<.
3
GGAAAAUCCCCUAUGCGAUAAAAAAGCGUUU
9 >>>...<<<..>>>...<<<..>>>...<<<

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

Автор:Бойко   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

Ограничения

N < 4000

L ≤ 100.

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

Входной файл (input.txt) Стандартный выход
1
>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

0.530s 0.018s 27