Фіксацыя памылак друку эвалюцыйным шляхам

Як паслядоўнасці ДНК вучылі нас перапісваць знакі стаянкі

Калі я вучыўся ў школе, я не праходзіў ніводнага класа па вылічальнай біялогіі. "Я не хачу працаваць у біятэхналагічнай кампаніі", - сказаў я. "Што гэта калі-небудзь зробіць для мяне?" Я па-ранейшаму не працую ў біятэхналогіі, але ўявіце маё здзіўленне, калі нейкі камп. Бія выскачыў у самых малаверагодных месцах: транскрыпцыя знакаў стаянкі.

Разумееце, каб закадзіраваць бардзюр, мы спачатку павінны былі высветліць, што сказана на ўсіх паркоўках. Каб зрабіць гэта добра, мы выкарыстоўвалі інструменты, якія былі створаны для разумення паслядоўнасці ДНК.

Якое дачыненне мае ДНК з знакамі стаянкі? Чытайце далей, каб даведацца!

Што кажа знак паркоўкі?

Падчас абследавання бардзюра мы фатаграфуем знакі стаянкі, падобныя ніжэй. Наступны крок - ператварыць яго ў тэкст, які мы можам інтэрпрэтаваць. Хоць аднойчы мы хочам зрабіць гэта з дапамогай камп'ютэрнага гледжання, у цяперашні час мы разлічваем на Amazon Mechanical Turk.

Знак паркоўкі ў Заходнім Галівудзе, Каліфорнія

Нашы работнікі выкарыстоўваюць вэб-інтэрфейс, каб увесці транскрыпцыі знакаў паркоўкі, як паказана вышэй. Але перапісваць знакі паркоўкі - цяжкая праца: яны могуць быць складанымі, а выявы могуць быць размытымі альбо інакш цяжка чытацца. Такім чынам, мы чакаем - і паглядзім - памылкі друку і іншую прапушчаную інфармацыю.

Атрыманне ўваходных дадзеных

Мы заўсёды адпраўляем кожны знак паркоўкі як мінімум двум работнікам. Такім чынам, мы заўсёды можам параўноўваць транскрыпцыі паміж сабой як асноўную праверку на правільнасць.

Першы крок, калі мы атрымліваем транскрыпцыю, гэта ачысціць яе. Мы праводзім усе вялікія літары, нармалізуем знакі прыпынку, выдаляем перапынкі радкоў і робім некаторыя іншыя відавочныя выпраўленні. Калі пасля ўборкі, двое работнікаў дакладна дамовяцца пра тое, што напісана на шыльдзе, мы скончылі! Калі няма, мы адпраўляем яго трэцяму рабочаму, а калі мы не можам дамовіцца з трыма працаўнікамі, адпраўляем яго яшчэ двум.

Але з трыма-пяццю работнікамі, бываюць выпадкі, калі кожны перапісчык вяртае крыху іншы адказ. Для знака вышэй, вось што мы атрымалі:

У гэтай сітуацыі транскрыпцыі досыць блізкія, каб мы маглі быць у стане іх супаставіць з чымсьці даволі дакладным. Але як?

Рэдагаваць адлегласць

Вельмі распаўсюджанай метрыкай пры апрацоўцы тэксту называецца адлегласць рэдагавання. Гэта найменшая колькасць зменаў, якія вы павінны ўнесці ў адзін фрагмент тэксту, каб ператварыць яго ў іншы. Напрыклад, ператварэнне CAT у GATE патрабуе двух правак: замена "C" на "G" і даданне "E" у канцы. Знаходжанне адлегласці для рэдагавання таксама паказвае, якія часткі паміж двума фрагментамі тэксту аднолькавыя (у дадзеным выпадку "AT").

Але што адбываецца, калі ў вас больш за два фрагменты тэксту? Мы можам абагульніць адлегласць рэдагавання, задаўшы пытанне: якія самыя невялікія змены мы можам зрабіць, якія робяць усе тэксты аднолькавымі? Напрыклад, скажам, мы пачалі з CAFE, GAFFE і CAFFEINE. Трэба было б адрэдагаваць усяго пяць знакаў (выдаліўшы INE з CAFFEINE, змяніўшы G на C у GAFFE і дадаўшы F у CAFE). Гэта таксама дазваляе пабудаваць выраўноўванне, якое адпавядае гэтым уваходам адзін да аднаго:

CAF.E ... GAFFE ... CAFFEINE

Калі мы зможам зрабіць так, каб зрабіць гэта для нашых транскрыпцый знакаў стаянкі, мы маглі б знайсці лепшае супадзенне. Вось як: кожная транскрыпцыя атрымлівае адзін "голас" пра тое, што знак кажа на кожнай пазіцыі, і мы прымаем большасць галасоў. (Калі не існуе большасці, мы адмаўляемся і кажам, што не можам знайсці правільны адказ). Калі большасць знакаў не маюць знакаў у дадзенай пазіцыі (напрыклад, для INE вышэй), мы проста выдаляем гэтыя сімвалы.

Існуе толькі адна праблема з гэтым алгарытмам: у той час як выраўноўванне дзвюх паслядоўнасцей лёгка, знайсці найлепшае выраўноўванне паслядоўнасці для больш чым двух паслядоўнасцей вельмі і вельмі цяжка! На самай справе гэта NP-складана, гэта азначае, што калі б мы ведалі, як гэта зрабіць эфектыўна, мы маглі б таксама эфектыўна вырашаць іншыя вельмі важныя праблемы інфарматыкі (напрыклад, праблема прадаўца і валодання цэлай колькасцю).

Бія на дапамогу

Аказваецца, мы не адзіныя з гэтай праблемай. Біёлагі сапраўды хочуць знайсці мутацыі ў паслядоўнасці ДНК. І аказваецца, што яны робяць гэта, выраўноўваючы шмат і шмат паслядоўнасцей ДНК і шукаючы, якія біты адрозніваюцца. Паколькі паслядоўнасці ДНК - гэта проста радкі персанажаў, гэта сапраўды такая ж праблема, як у нас! Як высвятляецца, калі я разглядаў гэтую праблему, мне пашчасціла сутыкнуцца з Роджэрам Крэйгам, які вучыў мяне пра метады, якія біяінфарматы выкарыстоўваюць для выраўноўвання паслядоўнасці ДНК і бялкоў.

Сапраўдная паслядоўнасць выраўноўвання амінакіслот у бялку паміж пяццю рознымі відамі млекакормячых.

Дык як яны гэта робяць? Памятаеце, што выраўноўванне адразу двух паслядоўнасцей проста. Такім чынам, калі вы можаце выраўнаваць дзве паслядоўнасці паміж сабой, а затым выраўнаваць вынік гэтага з трэцяй паслядоўнасцю і гэтак далей, вы можаце атрымаць агульнае выраўноўванне без асаблівых праблем.

Праблема заключаецца ў тым, у якім парадку вы вырабляеце выраўноўванне. Вы атрымліваеце значна лепшыя вынікі, калі спачатку выраўнаваць падобныя паслядоўнасці, перш чым перайсці да больш розных. У правільным парадку вы атрымаеце дрэва параўнанняў, якое выглядае прыблізна так:

Накіравальнае дрэва для выгляду ў вышэйпрыведзеным выраўноўванні

Гэта называецца "дрэва накіроўвалых", паколькі яно накіроўвае ваш шлях выраўноўвання паслядоўнасці. Біёлагам падабаецца мець гэта дрэва не толькі для стварэння расстаноўкі, але і для высвятлення эвалюцыйных сувязяў паміж рознымі паслядоўнасцямі ДНК!

Існуюць розныя метады пабудовы дрэў-накіроўвалых, большасць з якіх пачынаецца з першага пошуку ўсіх пары, рэдагаваць адлегласці паміж паслядоўнасцямі, і пачынаць з тых, якія бліжэй адзін да аднаго. Мы выкарыстоўваем сусед, які называецца.

Выраўноўванне, выкананае пры выкананні дрэва накіроўвалых, напэўна, не з'яўляецца аптымальным, але на практыцы аказваецца даволі ўдалым. У біялогіі ёсць метады, якія выкарыстоўваюць эўрыстыку для паляпшэння гэтага першапачатковага выніку, але мы выявілі, што вынік дастаткова добры, спыніўшыся тут.

Выраўноўванне ў дзеянні

Вернемся да нашага прыкладу, стэнаграмы вышэй:

Выкарыстоўваючы наш метад дрэва кіраўніцтва, мы б пачалі з выраўноўвання паслядоўнасцей 1 і 2, якія найбольш падобныя паміж сабой:

Тады мы зрабілі б паслядоўнасці 3 і 5:

Затым мы выраўнавалі б паслядоўнасць 4 з паслядоўнасцямі 1 і 2. Звярніце ўвагу, што адноснае выраўноўванне паслядоўнасцей 1 і 2 фіксавана, таму мы можам хутка выраўнаваць гэтыя паслядоўнасці.

Нарэшце, мы б сумясцілі паслядоўнасці 1, 2 і 4 з паслядоўнасцямі 3 і 5. Як і вышэй, фіксуецца адноснае выраўноўванне кожнага з гэтых набораў паслядоўнасцей.

І таму мы прыдумалі вынік:

Даволі добра! Праўда, мы прапусцілі «за выключэннем адзначанага ніжэй», паколькі гэта толькі ў двух з пяці стэнаграмаў.

Выснова

Калі мы пачалі збіраць дадзеныя аб бардзюры, мы ніколі не думалі, што гэта прывядзе нас да эвалюцыйнай біялогіі. Мы спадзяемся, што гэтая гісторыя паказвае, як нават такая простая праблема, як замацаванне друкарскіх памылак на паркоўцы можа стаць чымсьці вельмі глыбокім! Гэта заўсёды цікава, калі праца з, здавалася б, незвязаных абласцей спатрэбіцца, а ў інфарматыцы гэта адбываецца ўвесь час.

Якія праблемы, якія вы знайшлі для вырашэння іншых галін? Паведаміце нам на Twitter @coordcity @jacobbaskin.