Biyoinformatik | Dinamik Programlama (Dynamic Programming)


Ayşegül MURAT - Doktora Öğrencisi, Ege Üniversitesi Sağlık Biyoinformatiği A.B.D.

Bazı algoritmalar bir problemi daha küçük alt problemlere bölerek, daha büyük problemlerin çözümünü oluşturmak için oluşturulan bu küçük alt problemleri kullanır. Bu çözüm tekniğinin bölünen küçük alt problemlerin fazlalığı ve aynı alt problemleri çok kez çözmeye çalışmasıyla gereksiz süre artışına sebep olması gibi olumsuz yönü vardır. Dinamik programlama bu olumsuzluğu, bildiğimiz değerleri yeniden hesaplamaktan kaçınacak şekilde düzenleme yapar ve bu da çoğu zaman büyük ölçüde zaman kazancı olarak bize döner. [1]

Dinamik Programlama

Dinamik programlama, çoğu biyologlar tarafından gen fonksiyonu ve evrimsel tarih hakkında önemli çıkarımlar yapmak için kullanılan DNA sekans karşılaştırma algoritmalarını anlamak için bir bakış açısı sağlar. Yeni bir gen bulunduktan sonra biyologların genellikle onun işlevi hakkında hiçbir fikirleri olmaz. Yeni dizilenmiş bir genin işlevini anlamaya yönelik yaygın bir yaklaşım, işlevi bilinen genlerle benzerlikler bulmaktır. Benzerlik araştırması yoluyla kansere neden olan genler (1984 v-sis onkogeninin trombositten türetilmiş büyüme faktörü [PDGF] eşleşmesi) ile normal büyüme genleri arasında bir bağlantı kurmak ve kistik fibrozun (1989’da kromozom 7’de 1 milyon nükleotidlik bir bölgedeki ATP [Adenozin tirifosfatı] kodladığı bilinen gen ile benzerliklerinin keşfedilmesi) doğasını aydınlatmak, sekans karşılaştırmasında başarı hikayelerindendir. [1,2] Başka bir örnek ise miyoglobin ve hemoglobin zincirlerinin (alfa, beta ve diğerleri) yaklaşık 450 milyon yıl önce insan ve kıkırdakla balık soylarının birbirinden ayrıldığı zamana yakın bir zamanda ayrıldığı düşünülmektedir. Miyoglobin ve beta globin, X-ışını kristalografisi ile belirlendiği üzere çok benzer yapılara sahiptir. [1,2]

Manhattan Turist Problemi

Manhattan Turist problemi adı verilen problemin sekans hizalamasını tanımlamak için kullanılan bir sezgiye sahip olduğu bir şey okurken karşınıza çıkacaktır. New York City’nin Manhattan ilçesinde bir grup turist 59. Cadde ve 8. Cadde’nin köşesinden 42. Cadde ve Lexington Caddesindeki Chrysler Binası’na yürümeye kararlı olduğu bir gezi üzerinde duran bu problem, mümkün olduğunca çok ilgi çekici yer görmek isteyen turistlerin ya güneye ya da doğuya hareket etmesine izin verilmesiyle tam olarak kaç farklı yoldan seçim yapabilecekleriyle ilgilenir. Amaç en uygun yolda en fazla (mümkünse hepsi) sayıda bu caddelerdeki turistik yerlerin görülebilecek olmasıdır. Şekil 1-A’de, her bloktaki ilgi çekici yerlerin sayısını gösteren her satırın yanındaki sayılarla (ağırlık olarak adlandırılır), Şekil 1-B’deki gibi ızgara (grid) benzeri yapı şeklinde de gösterilebilir. Turistler, en kuzeybatı noktası (kaynak) ile en güneydoğu noktası (hedef) arasında birçok olası yol arasında karar vermelidir. Kaynaktan hedefe giden bir yolun ağırlığı, sadece kenarlarının ağırlıklarının toplam veya toplam ilgi çekici yer sayısıdır. Bu tür bir grafik, köşe dediğimiz sokakların kesişme noktalara ve sokakların kendisi olacak ve bunlarla ilişkili bir ağırlığa sahip olacaktır. Grafikteki yatay kenarların doğuya (sağ ok), dikey kenarların (aşağı ok) gibi güneye yönlendirildiğini varsayıyoruz. Bir yol, sürekli bir kenarlar dizisidir ve ilerlemenin uzunluğu boyunca ilerleme hızıdır. Manhattan Turist problemi, en fazla ilgi çekici yere sahip ola yolu yani en uzun yolu bulur. [1]


Şekil 1: Manhattan Turist problemi. [1]

DNA ve protein sekanslarında mutasyon evrimsel bir süreçtir; replikasyon hataları, nükleotidlerin ikamesine (substitution), eklenmesine (insertions) ve silinmesine (deletion), indel (insertions deletionun aynı anda olması) neden olur. Bir biyolog için bir mutasyonun sekans üzerinde nereye denk geldiğini çalışma yapılmadan önce bilme lüksü yoktur. 1966’da Vladimir Levenshtein, iki dizi arasındaki uzaklık mesafesi (edit distance) kavramını, bir diziyi diğerine dönüştürmek (baz ekleme veya silme) için gereken minimum düzenleme işlemi sayısı olarak açıklamıştır. Örneğin, TGCATAT beş düzenleme işlemiyle ATCCGAT'a dönüştürülebilir. Bu, TGCATAT ve ATCCGAT arasındaki düzenleme mesafesinin en fazla 5 olduğu anlamına gelir. Aslında, aralarındaki düzenleme mesafesi 4'tür çünkü bir hareket daha az hareketle birini diğerine dönüştürebilirsiniz. Şekil 2’de göreceğiniz Levenshtein ortaya koymuş olduğu uzaklık düzenlemeyi belirtilmiştir fakat Levenshtein bunu bir algoritmaya dönüştürmemiştir. Bunu çözümüyle ilişkili algoritmalar dinamik programlama algoritmalarıdır. [1,2]


ATATATAT'ın TATATATA'ya ve ATATATAT'ın TATAAT'ye hizalanması aşağıdaki gibidir. [1]





Levenshtein’ın beş düzenleme işlemiyle TGCATAT'ı ATCCGAT'a yapılabilir. [1]















V (n karakterlik) ve w (m karakterleri, m ile n’nin aynı olması gerekmez) dizelerinin hizalanması, iki satırlı bir matristir. Matris ilk satır sırasıyla v, w ve boşluk karakterlerini içerir. Her iki satırda da aynı harfi içeren sütunlara eşleşmeler (matches), farklı harfleri içeren sütunlara ise uyuşmazlıklar (mismatches) denir. Bir boşluk içeren hizalamanın sütunlarına indel adı verilen baz ekleme (insertions) ve baz silinmesi (deletion) durumlarında, üst satırda ekleme adı verilen bir boşluk (insertions için) ve alt satırda silme işlemlerinde bir boşluk (deletion için) tanımlanması bulunur. Hizalama matrisindeki iki satırın her biri, boşluk sembolleri “-” ile temsil edilir. Örneğin AT-GTTAT-, v = ATGTTAT’a karşılık gelen satırın temsilidir. ATCGT-A-A ise w= ATCGTAC’ a karşılık gelen satırın temsilidir. Şekil 2’de görselleştirilmesini görebilirsiniz. [1]


Şekil 2: V=ATGTTAT ve w= ATCGTAC için bir hizalama gridi. Her hizalama gridinde (0, 0) ila (n, m) arasındaki her yol bir hizalamaya karşılık gelir. [1]

Matristeki her sütun iki boyutlu bir n x m koordinattır; grid yapısı (0,0)’dan (n, m)’e kadar gösterilen bir Manhattan grid yapısına benzer olmasına rağmen temel fark bu matriste köşegen boyunca hareket edebilmemizdir. Bu matriste her kesişim noktası için bir tepe noktası eklenerek düzenleme grafiği oluşturulabilir. Herhangi iki dizi birbirine hizalanırken çok sayıda farklı hizalama matrisi ve en iyi hizalama yolu olabilir. Bunların bazılarında fazla sayıda uyumsuzluk (mismatches) ve indel veya az sayıda eşleşme olabilir. Bu duruma çözüm olarak matris içerisinde bir puanlama skoru belirtmektir. Kullanılabilir çeşitli puanlama sistemleri vardır ancak daha fazla eşleşme ile hizalamalara daha yüksek puanlar veren puanlama işlevsel olarak kullanılır. Her iki harf de aynıysa bir sütunu pozitif sayı, iki harf farklıysa negatif sayı olarak puanlar. Tüm hizalamanın puanı, ayrı sütun puanlarının toplamıdır. Kenarlara ağırlık puanı verilir, match için +1 puan verirken mismatch için 0 puan şeklinde basit bir puanlama skoru belirlenir ve böylece iki dizi arasında en uzun ortak alt diziyi bulma skorumuzu hesaplayabiliriz. Bu skor için “en uzun ortak altdizi (longest common subsequences)” hesaplanması yapılır. [1,2]





Referanslar

1. Jones, N. C., Pevzner, P. A., & Pevzner, P. (2004). An introduction to bioinformatics algorithms. MIT press.

2. Pevsner, J. (2015). Bioinformatics and functional genomics. John Wiley & Sons.