Дадлага 8

Дадлага 8. Хос дараалал харьцуулах динамик програмчлалын алгоритм

Оршил

Динамик програмчлалын алгоритм нь глобал болон локал гэсэн хоёр төрөл ба харгалзан Needleman-Wunsch ба Smith-Waterman алгоритм гэж нэрлэдэг. Эдгээр харьцуулалтад шаардлагатай хоёр хэмжигдэхүүн байдаг. Эхнийх нь 20 амин хүчил тус бүрийн хувьд эволюцийн явцад ямар амин хүчлээр солигдох боломжийг тооцоолж оноогоор илэрхийлсэн орлуулалтын матриц юм. PAM болон BLOSUM төрлийн хоёр матриц байдаг ба дараах зурагт BLOSUM62 матрицыг үзүүлэв.

Нөгөө нэг хэмжигдэхүүн нь харьцуулалтын үед дарааллуудад гарсан инсерци болон делецийг тооцох завсрын зайн торгууль юм. Хоосон зайн торгууль нь шугаман, affine болон ерөнхий функцийн гэсэн гурван төрөл байдаг. Үүнийг дараах зурагт үзүүлэв.

Эх сурвалж: Higgs and Attwood, Bioinformatics and Molecular Evolution.

Динамик програмчлалын алгоритм

Танай профессор өнөөдөр сүүлийн хугацаа нь дуусч байгаа тэтгэлгийн саналд (grant proposal) ашиглах зорилгоор өөр өөр зүйлээс ялгасан уургийн хоёр дарааллын хооронд харьцуулахыг хүссэн гэж үзье. Нийт сургууль сүлжээний түр засравтайгаас чи веб сервер ашиглан харьцуулах боломжгүй байв.

А. Needleman-Wunsch алгоритм болон BLOSUM62 матрицыг ашиглан доор үзүүлсэн уургийн хоёр богино дараалал дээр харьцуулалт хий. Динамик програмчлалын матрицыг үүсгэж бөглө. Хоосон зайн шугаман торгуулыг -6. Нэг нүднээс нөгөө нүдрүү хэрхэн явсныг үзүүл. Хамгийн сайн харьцуулалтыг харуулж чадах буцах шугамыг (traceback) зур. Матрицын дээд талд Дараалал-1, зүүн гар талд Дараалал-2-ийг байрлуул.

Дараалал-1 (Sequence 1): INMWGAF

Дараалал-2 (Sequence 2): VSTEWGD

Б. Танай профессорт өмнөх харьцуулалт хангалттай санагдаагүй учраас Смит-Водерманы (Smith-Waterman) алгоритмаар харьцуулахыг хүсэв. Энэ алгоритмыг ашигласаар (A) хэсгийн хариутай харьцуулахад үр дүн өөрчлөгдөж байна уу? Яагаад өөрчлөгдөв эсвэл яагаад өөрчлөгдөхгүй байна? Харьцуулалтын оноо хэрхэн өөрчлөгдөж байна вэ?

С. Танай профессор хариуг шалгаад яагаад PAM матрицыг ашиглалгүй, BLOSUM62 матрицыг ашиглан харьцуулалт хийснийг мэдэхийг хүсэв. Хийж байгаа харьцуулалтыг оруулан BLOSUM62 матриц болон PAM ийн төрлийн матрицын ялгааг тайлбарла.