Сгъни белтъка
По време на ученическите си години, Мечо Пух не намираше нищо интересно в учебниците по биология и химия. Откакто обаче Прасчо успя в домашни условия да синтезира всички видове мед, срещащи се в гората, Мечо се зарече да утрои годишния си добив, като измени генетичния материал на пчелите-майки, кодиран в аминокиселинни последователности. За целта е необходимо да се познава не само съставът на един белтък, но и неговото разположение. Евентуален провал би оставил Пух без мед в продължение на цяла година, и затова той изготви компютърен модел, който да намира най-вероятното разположение на белтъчна структура в равнината. Мечо се е погрижил да опрости модела, като е представил белтъка като последователност от хидрофобни(H) и полярни(P) аминокиселини и е задал енергията на пептидните връзки HH, HP и PP между две свързващи се аминокисилини, в зависимост от вида им. Всяка аминокиселина трябва да бъде самостоятелно поместена в клекта в квадратна решетка, така че всеки две съседни аминокиселини в белтъчната последователност да се намират в съседни клетки (т.е. с обща страна). Следвайки тенденцията в природата, максимизирайте сумата на енергиите на пептидните връзки, които се образуват само между аминокиселини в съседни клетки, които не са последователни в белтъчната структура.
На първия ред във входния файл protein.in, разделени с по един интервал, са записани четирите естествени числа: броят K(25≤K≤500) на аминокиселините в белтъчната последователност и енергиите на съответните връзки HH, HP и PP(0≤HH,HP,PP≤10). Следва ред с последователност от K символа ‘H’ и ‘P’ (номерирани от 1 до K), определящи вида на поредната аминокиселина в белтъка.
На първия ред в изходния файл protein.out трябва запишете естествените числа N и M(N, M≤500), задаващи големината на решетката, в която сте избрали да разположите белтъка. Следват N реда с по M естествени числа на всеки ред, всяко от които указва номера на аминокиселината, поместена в съответната клетка, или числото 0 за незаета клетка.
Примерен изход (не задължително оптимален):
3 4
3 4 5 6
2 9 8 7
1 0 0 0
Примерен вход:
9 1 0 2
HPPHPHHPH
Обяснение на примера:
Енергията на всяка от HH връзките e 1.
Енергията на всяка от HP връзките e 0.
Енергията на всяка от PP връзките e 2.
Номерацията на аминокиселините е:
123456789
HPPHPHHPH
Разположението на аминокиселините, предвид вида им (последователните аминокиселини са свързани с чертичка, а пептидните връзки са изобразени с диези):
P-H-P-H
| # # |
P#H-P-H
|
H . . .
Образуват се по една от всеки вид пептидни връзки (забележете, че една аминокиселина може да установи повече от една пептидна връзка), следователно сумата на енергиите на пептидните връзки е 1+0+2=3.
Сподели с приятели: |