Поравнавање вишеструких секвенци
Поравнавање вишеструких секвенци је поравнавање секвенци три или више биолошких секвенци, генерално протеина, ДНК, или РНК. У многим случајевима се подразумева да постоји еволуциони однос између секвенци које се поравнавају. Поравнавања више секвенци су полазна тачка за изучавање хомологије и даљу филогенетичку анализу. Визуелни приказ поравнавања је илустрација мутација, попут промена једне аминокиселине или нуклеотида, које са приказане као различита слова у датој колони поравнавања. Видне су и мутације уметања или брисања које су приказане као цртице у једној или више секвенци. Поравнавање вишеструких секвенци се често користи за процењивање конзервације протеинских домена, терцијарне и секундарне структуре, и индивидуалних аминокиселина или нуклеотида.
Поравнавање вишеструких секвенци се исто тако односи на сам процес поравнавања. Пошто је мануелно поравнавање три или више секвенци се биолошки релевантним дужинама непрактично, рачунарски алгоритми се увек користе за формирање и анализу поравнавања. Поравнавање вишеструких секвенци захтева софистицираније методологије од поравнавања пара секвенци, јер је оно рачунски комплексније. Већина програма за поравнавање вишеструких секвенци користи хеуристичке методе уместо глобалне оптимизације, јер је идентификација оптималног поравнавања између више од неколицине секвенци умерене дужине изузетно рачунски скупа.
Динамичко програмирање и рачунарска комплексност[уреди | уреди извор]
Директни метод за формирање поравнавања вишеструких секвенци користи технике динамичког програмирања за идентификацију глобално оптималних поравнавања. За протеине, овај метод обично користи две групе параметара: пенале празнина и супституционе матрице за додељивање вредности или вероватниће поравнавања сваког могућег пара аминокиселина. Ови параметри су базирани на сличности хемијских особина аминокиселина и еволуционој вероватноћи мутације. За нуклеотидне секвенце се користе слични пенали празнина, али су супституционе матрице знатно једноставније, типично се једино идентична преклапања узимају у обзир. Параметри у супституционој матрици могу да буду било сви позитивни, или мешавина позитивних и негативних у случају глобалног поравнавања. У случају локалног поравнавања они морају да буду позитивни и негативни.[1]
За н индивидуалних секвенци, за примену наивног метода је неопходно конструисати н-димензиони еквивалент матрице која се формира у стандардном поравнавању пара секвенци. Простор претраге се стога експоненцијално повећава са повећањем броја секвенци и веома је завистан од дужине секвенци. Наивном алгоритму је потребно О(ДужинаНсекв) време да произведе резултат. Налажење глобалног оптимума за н секвенци на овај начин је НП-комплетан проблем.[2][3][4]
На бази Карило-Липмановог алгоритма,[5] Алчал је увео 1989. практични метод који користи поравнавања парова за ограничавање н-димензионог простора претраге.[6] У овом приступу динамички програмирана поравнавања парова се изводе за сваки пар секвенци упитног сета, и претражује се једино простор у близини н-димензионог пресека тих поравнавања. Овај програм оптимизује суму свих парова слова у свакој позицији поравнавања (такозвани параметар суме парова).[7]
Референце[уреди | уреди извор]
- ^ „Хелп wитх матрицес усед ин сеqуенце цомпарисон тоолс”. Еуропеан Биоинформатицс Институте. Архивирано из оригинала 11. 03. 2010. г. Приступљено 3. 3. 2010.
- ^ Wанг L, Јианг Т (1994). „Он тхе цомплеxитy оф мултипле сеqуенце алигнмент”. Ј Цомпут Биол. 1 (4): 337—348. ПМИД 8790475. дои:10.1089/цмб.1994.1.337.
- ^ Јуст W (2001). „Цомпутатионал цомплеxитy оф мултипле сеqуенце алигнмент wитх СП-сцоре”. Ј Цомпут Биол. 8 (6): 615—23. ПМИД 11747615. дои:10.1089/106652701753307511.
- ^ Елиас, Исаац (2006). „Сеттлинг тхе интрацтабилитy оф мултипле алигнмент”. Ј Цомпут Биол. 13 (7): 1323—1339. ПМИД 17037961. дои:10.1089/цмб.2006.13.1323.
- ^ Carrillo H, Lipman DJ,(1988) The Multiple Sequence Alignment Problem in Biology. SIAM Journal of Applied Mathematics, Vol.48, No. 5, 1073-1082
- ^ Липман ДЈ, Алтсцхул СФ, Кецециоглу ЈД (1989). „А тоол фор мултипле сеqуенце алигнмент”. Проц Натл Ацад Сци У С А. 86 (12): 4412—4415. ПМЦ 287279
. ПМИД 2734293. дои:10.1073/пнас.86.12.4412.
- ^ „Генетиц аналyсис софтwаре”. Натионал Центер фор Биотецхнологy Информатион. Приступљено 3. 3. 2010.
Литература[уреди | уреди извор]
- Дурет, L.; С. Абдеддаим (2000). „Мултипле алигнмент фор струцтурал фунцтионал ор пхyлогенетиц аналyсес оф хомологоус сеqуенцес”. Ур.: D. Хиггинс анд W. Таyлор. Биоинформатицс сеqуенце струцтуре анд датабанкс. Оxфорд: Оxфорд Университy Пресс.
- Нотредаме, C. (2002). „Рецент прогрессес ин мултипле сеqуенце алигнмент: а сурвеy”. Пхармацогеномицс. 31 (1): 131—144. ПМИД 11966409. дои:10.1517/14622416.3.1.131.
- Тхомпсон, Ј. D.; Ф. Плеwниак; О. Поцх (1999). „А цомпрехенсиве цомпарисон оф мултипле сеqуенце алигнмент програмс”. Нуцлеиц Ацидс Ресеарцх. 27 (13): 12682—2690. ПМЦ 148477 . ПМИД 10373585. дои:10.1093/нар/27.13.2682.
- Wаллаце, I.M.; Блацксхиелдс Г; Хиггинс ДГ. (2005). „Мултипле сеqуенце алигнментс”. Цурр Опин Струцт Биол. 15 (3): 261—266. ПМИД 15963889. дои:10.1016/ј.сби.2005.04.002.
- Нотредаме, C (2007). „Рецент Еволутионс оф Мултипле Сеqуенце Алигнмент Алгоритхмс”. ПЛОС Цомпутатионал Биологy. 8 (3): е123. ПМЦ 1963500 . ПМИД 17784778. дои:10.1371/јоурнал.пцби.0030123.
Спољашње везе[уреди | уреди извор]
- ExPASy Архивирано на сајту Wayback Machine (13. април 2010)
- Поравнавање вишеструких секвенци