XIV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

В шестия задочен кръг на конкурса по програмиране победител стана Румен Христов, чието решение показа най-добър резултат. Румен ще бъде награден в рамките на финалния присъствен кръг, който ще се състои на 20 май в София. Предлагаме на вашето внимание анализа на задачата, подхода за решаването й, написан от победителя в кръга.Задача 6 – Сгъни Белтъка Анализ от Румен ХристовЗа решаването на шестата задача никой от участниците не намери достатъчно добър евристичен алгоритъм и затова начело на класирането се оказахме шестима човека, които бяхме реализирали решения на практика с една и съща идея, често използвана при решаване на полиномиално разрешими задачи – динамично програмиране. Решението с динамично програмиране използва малка част от позволеното време и затова можеше да се приложат различни техники за подобряване на резултата в остащите 3-4 секунди. В моя случай през това време просто развалях положението на последните 15 аминокиселини и ги подреждах по по-оптимален начин, което ми даде известно преимущество пред останалите участници. Друг вариант беше да се изпробва спираловидна наредба на аминокиселините или пък различни greedy алгоритми, но всъщност тези решения много рядко даваха по-добри резултати от динамичното.

Накратко ще представя как може да се използва динамично програмиране в случая: нареждаме аминокиселините ред по ред, т.е. ако знаем, че на миналия ред сме наредили аминокиселините с номера от X до Y, то на следващия ред ще трябва да разположим аминокиселините с номера от Y+1 до някое Z. Ако например на миналия ред са аминокиселините от 5 до 9, на текущия – от 10 до 16, а на следващия – от 17 до 19, то подреждането ще има следния вид:

Ред1: 5 6 7 8 9
Ред2: 16 15 14 13 12 11 10
Ред3: 17 18 19

След всеки подреден ред обръщаме посоката, по която нареждаме аминокиселините. За всеки интервал на аминокиселините от X до Y на един ред искаме да изчислим кой е интервалът отаминокиселини, които трябва да разположим на следващия ред, така че той да ни донесе най-голяма енергия оттук до края на белтъка (от Y+1 до N) при вече подредени първите Y аминокиселини. Така, ако на един ред разположим аминокиселините от X до Y, с F(X,Y) означаваме максималната възможна енергия на връзките, които могат да образуват следващите аминокиселини, следвайки същата стратегия. Оттук следва рекурентната формула F(X,Y) = max[F(Y+1, I) + CurrentEnergy], където CurrentEnergy е енергията на пептидните връзки между двойките клетки от следващия и от текущия ред, които имат обща страна. Остава да намерим това I, за което функцията F(X,Y) приема възможно най-голяма стойност: обхождаме всички I(Y<I) и за всяко смятаме F(Y+1, I) и CurrentEnergy.

За примера по-горе, CurrentEnergy за двойките аминокиселини от първия и втория ред, е сумата на енергиите между аминокиселините 9 и 10, 8 и 11, 7 и 12, 6 и 13, 5 и 14. За да не изчисляваме многократно стойността на тази функция F(X,Y) при едни и същи X и Y, можем да запомним максималната стойност, след като веднъж сме я изчислили. Тази оптимизация позволява сложността на алгоритъма да се сведе до полиномиална – O(n3) – за всеки два края на интервал, избираме до коя аминокиселина да бъдат разположени на следващия ред, като успоредно смятаме енергията на пептидните връзки между двата реда. Граничните ни случаи са F(X,N)=0 за всяко X, т.е. подредили сме всички елементи, като последният ред съдържа аминокиселините от X до N.В края на алгоритъма максималната енергия на намерено от нас разположение на белтъка е максималното F(1,X) за всяко X. За възстановяване на самото разположение всеки път, когато оптимизираме функцията F(X,Y) по време на алгоритъма, запомняме от какъв следващ ред сме получили тази оптимална стойност.

Информация за човешките белтъци, които са ползвани при изготвяне на тестовете:

test#1: 110acids 37.27% polar, proinsulin precursor
test#2: 154acids 49.35% polar, myoglobin
test#3: 183acids 60.66% polar, ferritin, heavy polypeptide 1
test#4: 263acids 48.29% polar, ribosomal protein S4
test#5: 377acids 49.07% polar, cardiac muscle alpha actin 1
test#6: 372acids 49.19% polar, selectin L precursor
test#7: 430acids 57.91% polar, keratin 18
test#8: 445acids 50.56% polar, tubulin, alpha 3e
test#9: 461acids 48.59% polar, protein C
test#10: 477acids 29.14% polar, solute carrier family 2