Çoklu Dizi Hizalaması

Çoklu Dizi Hizalaması

Çoklu Dizi Hizalaması Nedir - Çoklu Dizi Hizalaması Hakkında - Çoklu Dizi Hizalaması Tanımı

Çoklu dizi hizalaması, üç ya da çok biyolojik dizinin (genelde protein, DNA veya RNA dizisinin) dizi hizalamasıdır Çoğu durumda, girdi kümesindeki sorgu dizilerinin evrimsel bir ilişkiye sahip olduğu, yani ortak bir ataya sahip oldukları varsayılır Elde edilen çoklu dizi hizalamasından homoloji olduğu çıkarımı yapılabilir ve filogenetik analiz ile dizilerin evrimsel kökenleri değerlendirilebilir Hizalamanın sağdaki resimdeki gibi gösterimiyle noktasal mutasyonlar, hizalamadaki sütunlardan birinde farklı bir harf olarak, ensersiyon ve delesyonlar ise hizalamadaki satırlardan bir veya daha fazlasında tire şeklinde beliren eklemeler şeklinde mutasyon olayları görülebilir Protein bölgelerinde, ikincil veya üçüncül yapılarda ve hatta bireysel amino asit veya nükleotitlerin dizi korunumunu değerlendirmek için çoklu dizi hizalamaları sıkça kullanılır

Çoklu dizi hizalaması terimi ayrıca bir dizi kümesinin hizalanması süreci için kullanılır Üç veya daha çok dizinin elle hizalanması zor olduğu ve genelde çok zaman alıcı olduğu için hizalamaların üretim ve analizi için berimsel (hesaplamalı) algoritmalar kullanılır ÇDH'ler ikili dizi hizalamasından daha ileri yöntemlerin kullanımını gerektirir çünkü berimsel olarak karmaşıktırlar Nispeten kısa birkaç diziden fazlasının optimal hizalamasını bulmak berimsel bakımdan çok pahalıdır, bu yüzden çoğu çoklu dizileme programları global optimizasyon yerine höristik yöntemler kullanır

Çeşitli organizmaların ribozom proteini P0 (L10E)'ın çoklu dizi hizalamasının ilk 90 pozisyonu ClustalX ile elde edilmiştir

Dinamik programlama ve berimsel karmaşıklık

Bir ÇDH üretiminde global optimal çözümünü bulmak için dinamik programlama tekniği kullanılır Proteinler için, bu yöntem iki parametre grubu kullanılır: bir boşluk cezası ve bir substitusyon matrisi Substitusyon matrisi, her bir amino asit çiftinin birbiriyle hizalanmasına karşılık gelen bir puan (skor) veya olasılık değeri içerir, bu değerler amino asitlerin kimyasal özelliklerinin benzerliğine ve mutasyonun olmasının evrimsel olasılığına dayalıdır Nükleotit dizileri için benzer bir boşluk ceza değeri vardır ama substitusyon matrisi çok daha basittir, tipik olarak sadece aynı olma veya olmamaya göre skorlar bulunur Substitusyon matrisindeki skorlar global hizalamalar durumunda ya sırf pozitif olabilir veya hem pozitif hem negatif değerler içerebilirler, ama lokal hizalama durumunda hem pozitif hem negatif değerler içermek zorundadır

İki dizinin hizalanmasında bir matris kullanılmasından yola çıkarak, n adet dizinin hizalanması için, o matrisin n-boyutlu karşılığı bir matris kullanmak, çözüme ulaşmanın toy (saf) bir yolu olur Bu yaklaşımın sonucu arama uzayı artan n ile üssel şekilde büyür ve dizi uzunluğuna da kuvvetle bağımlıdır Berimsel karmaşıklığı ölçmekte kullanılan büyük O notasyonu ile ifade edilirse, toy yaklaşımla elde edilmiş bir ÇDH n dizi için O(Uzunlukn) sürede tamamlanır Bu n dizi için global optimumu bulmanın NP-tam problem olduğu gösterilmiştir Altschul, 1989'da, Carrillo-Lipman Algorithmasını kullanarak, n-boyutlu arama uzayının ikili hizalamalar yaparak sınırlanabileceğini göstermiştirBu yaklaşım ile, sorgu kümesindeki her bir dizi çifti için dinzmik programlama hizalamaları yapılır, sonra bu hizalamaların n-boyutlu kesişimi civarında n-li hizalama için arama yapılır Bu ÇDH algoritması hizalamadaki her pozisyon için, karakter çiftlerinin toplamlarını (çiftler toplamı skorunu) optimize eder Algoritma, çoklu dizi hizalaması yapan bir yazılım programı olarak uygulamaya sokulmuştur

İlerleyici hizalama inşası

Çoklu dizi hizalamasında en yaygın kullanılan yöntem, ilerleyici (İng progressive) yöntem olarak bilinen (hiyerarşik veya ağaç yöntemi olarak da bilinir) bir buluşsal (höristik) aramadır Bu yöntemde, ÇDH'yi inşa etmek için önce birbirine en benzer olan çiftten başlanır, sonra gittikçe daha az benzeşen çiftler eklenir İlerleyici hizalama yöntemlerinin hepsi iki aşamadan oluşur: diziler arasındaki ilişkinin kılavuz ağaç denen bir filogenetik ağaç olarak gösterildiği birinci aşama; ve büyüyen ÇDH'ye dizilerin sırayla eklenerek ÇDH'nin inşa edildiği bir ikinci aşama İlk kılavuz ağacı oluşturmak için, dinamik programlama hizalaması yapmak yerine, verimli bir kümeleme (clustering) yöntemi kullanılır (komşu birleştirme veya UPGMA gibi) Kümelemede uzaklık değeri olarak aynı iki harfli altdizilerin sayısı kullanılabilir (FASTA programında olduğu gibi)

İlerleyici hizalamalar global optimal olamaz Temel sorun, ÇDH oluşturulurken yapılan hataların nihai sonuca kadar taşınmasıdır Kümedeki diziler birbirlerine uzaktan ilişkiliyse algoritmanın performansı özellikle kötüdür Çoğu modern ilerleyici yöntemler, sorgu kümesinin her bir üyesi için skor fonksiyonlarını değiştirir Bu değişken skor, dizilerin en yakın komşularına olan genetik uzaklığına bağlı olarak nonlineer değişen bir ağırlık fonksiyonuyla hesaplanır Böylece, hizalama programının dizileri rastgele olmayan bir şekilde seçmesinin etkisi düzeltilmiş olur

İlerleyici hizalama yöntemler, çok sayıda (yüzlerce ila binlerce arası) diziye uygulanabilecek derecede verimli çalışırlar İlerleyici hizalama hizmetleri kamuya açık Web sunucularında mevcuttur, bu yüzden kullanıcılar bu programı kendi bilgisayarlarında kurmak zorunda değildirler En popüler ilerleyici hizalama yöntemi Clustal ailesi olmuştur, özellikle ağırlıklı versiyonu olan clustalW bunlara çeşitli Web portallerindan erişilebilir (GenomeNet, EBI, and EMBNet dahil olmak üzere) Farklı portaller veya uyarlamalar kullanıcı arayüzü ve kullanıcının değiştirebileceği parametreler bakımından faklılık gösterebilirler ClustalW'nun doğrudan filogenetik ağaç inşası için kullanılmaması gerektiğine dair programcının açık ikazlarına rağmen, programın çıktıları bu amaç için yaygın olarak kullanılır ClustalW çıktısı, homoloji modellemesi ile protein yapı öndeyisine girdi olarak da kullanılmamalıdır

T-Coffee olarak adlandırılan bir diğer yaygın ilerleyici hizalama yöntemi, Clustal ve onun türevlerinden daha yavaştır ama birbiriyle uzaktan ilişkili diziler için daha doğru hizalamalar üretir İkili hizalamalar hesaplamak için T-Coffee iki farklı yöntemle elde edilen hizalamaları birleştirir: çiftin doğrudan hizalaması ve, çiftteki her diziyi üçüncü bir dizi ile hizalanması ile elde edilen, indirekt hizalamalar Bu program, hem Clustal çıktısını, hem de başka bir lokal hizalama programı olan ve iki dizideki çoklu lokal hizalanma bölgeleri bulan LALIGN programını kullanır Elde edilen hizalama ve filogenetik ağaç, yeni ve daha doğru ağırlık faktörleri üretmek için kullanılır

İleleyici yöntemler buluşsal oldukları için, global bir optimuma yakınsama garantileri yoktur, hizalamanın kalitesini değerlendirmek zor olabilir ve gerçek biyolojik anlamı belirsiz olabilir

Tekrarlayıcı yöntemler

ÇDH üretip, ilerleyici yöntemlere özgü hataları azaltan bir yöntemler grubu "tekrarlayıcı" (iterative) olarak sınıflandırılmıştır, çünkü bunlar ilerleyici yöntemlere benzer olarak çalışmakla beraber, büyüyen ÇDH'ye yeni diziler eklerken ilk dizileri tekrar tekrar hizalamaya devam eder İlerleyici yöntemlerin yüksek kaliteli ilk hizalamalara muhtaç olmalarının nedeni, bu hizalamaların hep nihai sonuçta yer almasıdır Yani bir dizi bir ÇDH içinde yerini aldıktan sonra onun hizalaması tekrar gözden geçirilmez Bu yaklaşıklık (approximation) berimsel hızı artırır ama doğruluktan kaybetme pahasına Buna karşın, tekrarlayıcı yöntemler, daha önce hesaplanmış ikili hizalamalara veya sorgu dizisini içeren alt-ÇDH'ler geri gelebilirler Bu sayede, yüksek kaliteli bir hizalama skoru elde etmeyi sağlayacak bir genel objektif fonksiyon optimize edilebilir

Birbirinden ince farklılıklar gösteren çeşitli tekrarlayıcı yöntemler uygulamaya konmuş ve yazılım paketi olarak kullanıma sunulmuştur; bu yazılımlar hakkında çeşitli inceleme ve kıyaslama makaleleri "en iyi" yöntemi ilan etmekten kaçınmışlardır[10] PRRN/PRRP adlı yazılım paketi bir tepe tırmanma algoritması kullanır, ÇDH hizalama skorunu optimize etmek için büyüyen ÇDH'nin hem hizalama ağırlıklarını hem de yerel olarak ıraksamış veya "boşluklu" bölgelerini tekrarlayan bir şekilde düzeltir PRRP, daha hızlı bir yöntemle inşa edilmiş bir hizalamayı iyileştirmede kullanıldığında en iyi performans gösterir

Başka bir tekrarlayıcı program, DIALIGN, ise olağandışı bir yaklaşım kullanır, boşluk cezası kullanmadan dizi motifleri veya alt dizilerin lokal hizalamalarına odaklanır İkili hizalama yapmakta kullanılan bir nokta matris grafiğine benzer bir matris gösterimi kullanılarak bireysel motifler hizalanır Yavaş bir global hizalama için hızlı lokal hizalamaları birer "tohum" olarak kullanan bir alternatif yöntem CHAOS/DIALIGN paketinde kullanılır

Tekrarlama-temelli üçüncü bir popüler yöntem MUSCLE (multiple sequence alignment by log-expectation; log-beklenti ile çoklu dizi hizalaması) olarak adlandırılır, iki dizinin yakınlığını belirlemek için daha doğruluklu bir uzaklık değeri hesaplayarak, ilerleyici yöntemlerden daha yüksek bir başarı gösterir Uzaklık ölçütü, tekrarlama aşamaları arasında yenilenir