Прилича на ДНК код, търси се престъпника, който открадна хонорара на Рабин :)
Задача НЕ за интервю
0 1 2 3 4 5 6 7 ...9 10 11 12 13 ...22 23 24 25 26 ...32 33 34 35 36
Не знам кой ми е сменил името на темата, но очевидно няма никой който да ми свърши работатата тук. :)
Даже на Python и SQLite ще поне 3-пъти по-бързо от твоето решение, което е по-скоро "тешкарско" отколкото да върши някаква реална работа. 10-на реда код е.
Все още чакам демонстрацията. :) Ама нещо се умълчаха всички като дадох данните. :)
Данните са за това, да са в база - база данни. Не ти звучи логично? 966MB не ме плашат, нито 966GB, важно е как са организирани и какво се търси в тях.
Пак празни приказки и никакви числа. Типично за тълпата "да, ама..." :)
Събирам кураж. Тва ще стане доста стегнато с авх. Но е за гпу. Там ще блесне векторната архитектура.
Да, следобед или в краен случай утре ще се забавлявам с CUDA.
А всъщност защо се счита че левенщайн дистанцията показва там каквото се счита че показва?
Не съм сигурен, че разбирам въпроса. При синтезирането, копирането и четенето на ДНК се получават грешки. Те могат да доведат до добавяне, изтриване или замяна на нуклеотиди. Левенщайн е edit distance - показва какъв е минималния брой грешки, които има. Младежа статистик още не може да преживее, че няма как да различи insert+delete от replace.
Когато се копира ДНК-то в клетките, освен ензима за копиране има и още един, който проверява дали копирането е вярно (proofreading), но засега не се използва от хората в лабораториите, не знам защо.
Левенщайна дава колко операции insert, delete, replace трябва да се направят за да е докара единия стринг до другия.
Тука понеже се иска над 100 да ги игнорира, това не може ли да се използва за специална версия на левенщайн, която при очевидно различни стрингове с дистанция над 100 (или там колкото се подаде за max) да не изчислява точното разстояние, а да връща веднага някакво по-голямо от 100 разстояние, като вид оптимизация. Или да се ползва заедно с по-лек алгоритъм(Soundex ?), който да е способен да връща само съмнително близки стрингове, които допълнително да се подават на Левенщайн за точно разстояние, а очевидно далечните да ги реже бързо.
Когато имаш само 4 букви в азбуката, и позволяваш до 80% грешки, е доста трудно да отрежеш нещо. :) Иначе търсенето с trie позволява да се зададе максимално разстояние.
ДНК-то си е доста стабилна молекула, тя не се уврежда толко лесно и не знам защо Левенщайн въобще носи такава асоциация (аз никога не съм го приемал за нещо различно от свързано с низове и евентуално чисто човешки грешки при въвеждането им). При ДНК-то реално няма особено много от тези проблеми, проблемите са при транскрипцията и транслацията на ДНК-то, там е където грешките предимно стават. Самото ДНК и да се уврежда, се уврежда с порядъци по-рядко, отколкото грешките които се случват когато части от ДНК се довежда до РНК, а от въпросното РНК се синтезират белтъци. Обаче там играта е доста по-сложна и на някои грешки би трябвало да им се сложи "тегло" най-малкото и това тегло е сложно и зависи и от "историята", примерно грешка след инициращ кодон е далеч по-фатална или пък гейк инициращ кодон е значително голям проблем.
Синтезирането на ДНК се прави чрез добавяне на нуклеотид един по един, или от ензим или от някакъв друг химически процес (имаше там някакви deprotection, elongation, и т.н.), чието име забравих в момента. Понякога вместо един нуклеотид се добавят два, понякога николко. Замяната става по-рядко, или ако реагентите не са чисти, или ако остане реагент от предишния цикъл.
Умножаването на ДНК (по това време на пандемията предполагам, че всеки вече е чувал за PCR) се прави от ензим и той може да сгреши, защото не се използват ензимите, които правят proofreading. Отделно има забавни ефекти когато има secondary structures, с различни G-quadruplex, hairpins и т.н.
Четенето на ДНК-то се прави чрез копиране, пак от ензими. Там, освен всичко друго има и камери които се опитват да разпознават цвят.
Има и нанопори, но там положението е още по-зле. :)
Е деленето на клетката и съответно на ДНК-то разпъването, не е лишено от грешки - иначе немаше да има старееене, злокачествени заболявания и прочее. Но тези грешки се случват относително рядко на фона на другите, свързани с възпроизвеждането на кодираните протеини. Аз и не казвам кое е по-лошо за организма, организмите са зловещо сложни неща. Просто докато се копират книгите, има доста по-малко грешки, отколкото при четенето им с разбиране. В лошият случай при транскрипцията и транслацията, грешките завършват с клетъчна смърт което така или иначе не е чак толкова голяма работа, милиарди клетки има в организма, една умряла, голям праз.
А аз изобщо не говоря за организми, а за синтез на ДНК от хора в лаборатория. :)
Иначе, не случайно чета An Introduction to Systems Biology: Design Principles of Biological Circuits. :) Може да е 50 години в бъдещето, но ще направим от клетките massively parallel supercomputers :)
Ааааа ееее не знам, не разбирам от това и за какво е борбата там, говоря от гледна точка на нашата скромна природа, извращения детски де, не би трябвало да ми е интересно, у младежките си години тея неща силно ме вълнуваха, сега не много. Иначе човек наистина може много вдъхновение да черпи от мащехата природа, примерно как 64 различни кодона кодират само 20 различни аминокиселини и защо специално за част от тях redundancy-то е доста никакво в сравнение с други, нищо не е случайно на тоя свят.
0 1 2 3 4 5 6 7 ...9 10 11 12 13 ...22 23 24 25 26 ...32 33 34 35 36