Техническое задание.
Терминология:
- вес выравнивания – это число, которое характеризует качество выравнивания. Оно является суммой весов попарных соответствий для каждой позиции выравнивания за вычетом штрафов за гэпы.
- удельный вес выравнивания – это вес выравнивания, делённый на длину выравнивания.
Краткое описание программы:
Программа состоит из двух частей: задача первой оценить, есть ли выравнивание между двумя последовательностями, задача второй части – анализ множественного выравнивания (построение графа, отображающего наличие попарных выравниваний, поиск клик и компонент связности в нем)
Часть 1: check_align
Входные данные: белковое выравнивание двух последовательностей в FASTA-формате.
Выходные данные: оценка достоверности выравнивания:
- ответ да/нет;
- вес выравнивания (score)
Программа предоставляет интерфейс командной строки.
Интерфейс: check_align.py [опции] имя_входного_файла.fasta
Опции:
- --scoring matrix, --matrix, -m. Файл матрицы попарных соответствий. По умолчанию используется встроенная матрица BLOSUM62;
- --gap-open-penalty, -g. Штраф за первую позицию гэпа. По умолчанию: -10.
- --gap-extend-penalty, -e. Штраф за каждую позицию гэпа, кроме начальной или конечной. По умолчанию: -0.5.
- --threshold, -t. Пороговое значение. Если удельный вес выравнивания превышает порог, то мы предполагаем, что выравнивание есть. По умолчанию: 1.
- --machine-readable. Выдавать результаты в формате, удобном для использования другими программами (без текстовых комментариев). По умолчанию: нет.
Выходные данные выводятся на экран.
Пример:
Alignment is valid, it’s score is ???
Часть 2: multi_align
Входные данные: множественное белковое выравнивание последовательностей в FASTA-формате.
Выходные данные:
- Информация о крайних случаях: все последовательности выровнены друг с другом или ни одна из последовательностей не выровнена ни с одной.
- В зависимости от флагов выдаются клики графа соответствия или его группы связности.
- В зависимости от флагов выдача идет в виде FASTA-файлов или в виде списков заголовков последовательностей, для клики выдается вес выравнивания (score).
Программа предоставляет интерфейс командной строки.
Интерфейс: multi_align.py [опции] имя_входного_файла.fasta
Опции:
- --scoring matrix=matrixfile, --matrix, -m. Файл матрицы попарных соответствий. По умолчанию используется встроенная матрица BLOSUM62;
- --gap-open-penalty=value, -g. Штраф за первую позицию гэпа. По умолчанию: -10.
- --gap-extend-penalty=value, -e. Штраф за каждую позицию гэпа, кроме начальной или конечной. По умолчанию: -0.5.
- --threshold=value, -t. Пороговое значение. Если удельный вес выравнивания превышает порог, то мы предполагаем, что выравнивание есть. По умолчанию: 1.
- --clicques, -q. Выдавать информацию о кликах в графе соответствия.
- --connected-components, -c. Выдавать информацию о группах связности в графе соответствия
- --fasta=name format, -f. printf-style шаблон имен файлов для записи результатов в FASTA-файлы
- --quiet. Не выводить на экран выходные данные (для автоматического режима, вместе с ключом –fasta).
Выходные данные по умолчанию выводятся на экран.
Общие требования
Программа должна сопровождаться текстом с комментариями о назначении и об используемых алгоритмах.
Каждая функция должна сопровождаться тестами doctest.
Текст программ оформляется в соответствии с PEP8.
Приложение 1. Описание формата FASTA
Only the "concatenated Fasta" format is acceptable. A greater than symbol (>) at the first column indicates that a new sequence begins from the next line. The name of the sequence (less than or equal to 10 characters) must immediately follow (>). A double slash (//) indicates the end of a sequence, but usually you can omit it. A line starting with a semicolon (;) is a comment line. Each line should not exceed 255 characters in length.
All IUPAC-IUB codes for both amino acids and nucleotides are recognized, except for the amino-acid code 'U' for selenocysteine. In addition to dash (-), asterisk (*) is also regarded as a deletion character in an amino-acid sequence. Other characters, including dot (.) and space ( ), are simply disregarded.
An example of the format is shown below.
>Seq1 ; This is a comment line ACMGRSVTWYHKDBN >Seq2 ACVTWYHKDBN //
Приложение 2. Матрица соответствий аминокислотных подстановок.
Score matrix of amino-acid substitutions. Substitution matrix describes the rate at which one character in a sequence changes to other character states over time. The probabilities used in the matrix calculation are computed by looking at "blocks" of conserved sequences found in multiple protein alignments. These conserved sequences are assumed to be of functional importance within related proteins.
A R N D C Q E G H I L K M F P S T W Y V B Z X A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0 -2 -1 0 R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3 -1 0 -1 N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3 3 0 -1 D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3 4 1 -1 C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2 0 3 -1 E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2 1 4 -1 G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3 -1 -2 -1 H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3 0 0 -1 I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3 -3 -3 -1 L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1 -4 -3 -1 K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2 0 1 -1 M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1 -3 -1 -1 F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1 -3 -3 -1 P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2 -2 -1 -2 S 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2 0 0 0 T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0 -1 -1 0 W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3 -4 -3 -2 Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 -1 -3 -2 -1 V 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4 -3 -2 -1 B -2 -1 3 4 -3 0 1 -1 0 -3 -4 0 -3 -3 -2 0 -1 -4 -3 -3 4 1 -1 Z -1 0 0 1 -3 3 4 -2 0 -3 -3 1 -1 -3 -1 0 -1 -3 -2 -2 1 4 -1 X 0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 0 0 -2 -1 -1 -1 -1 -1
Note: X denotes an unidentified/other symbol.