Dizi Hizalama Algoritmaları
Dizi hizalama algoritmaları, iki dizgi arasındaki benzerliği, eklemeler, silmeler ve değiştirmeler üzerinde dinamik programlama yöntemini kullanarak birini diğerine dönüştürmenin en düşük maliyetli yolunu bulmak suretiyle ölçmekte ve görselleştirmektedir.
Tanım
Dizi hizalama, boşluklar ekleyerek ve karakterleri eşleştirerek, eşleştirmeyerek veya değiştirerek iki (veya daha fazla) dizginin karşılıklılığını en üst düzeye çıkarmak için yapılan bir düzenlemedir; bir hizalama algoritması, genellikle dinamik programlama aracılığıyla, belirli bir maliyet veya puanlama modeli altında optimal bir hizalamayı ve puanını hesaplamaktadır.
Kapsam
Bu konu, dizgileri karşılaştırmaya yönelik dinamik programlama algoritmalarını kapsamaktadır: düzenleme (Levenshtein) mesafesi ve en uzun ortak alt dizi, global hizalama (Needleman-Wunsch), lokal hizalama (Smith-Waterman) ve biyolojik hizalamaları şekillendiren puanlama şemaları (boşluk cezaları, ikame matrisleri). Konu, temel tekrarlamayı ve bunun karesel zaman ve alan maliyetini, ayrıca alan tasarrufu sağlayan iyileştirmeleri ele almaktadır. İndeks tabanlı ve tam eşleşen yöntemler ilgili konularda işlenmektedir.
Temel sorular
- İki dizgi arasındaki benzerlik, düzenleme mesafesi veya hizalama puanı olarak nasıl nicelleştirilmektedir?
- Dinamik programlama tablosu optimal bir hizalamayı nasıl hesaplamaktadır?
- Global hizalamayı lokal hizalamadan ayıran nedir ve her biri ne zaman uygun olmaktadır?
- Boşluk cezaları ve ikame matrisleri, ortaya çıkan hizalamayı nasıl etkilemektedir?
- Uzun diziler için karesel alan gereksinimi nasıl azaltılabilmektedir?
Anahtar kavramlar
- düzenleme (Levenshtein) mesafesi
- en uzun ortak alt dizi
- global hizalama
- lokal hizalama
- Needleman-Wunsch algoritması
- Smith-Waterman algoritması
- boşluk cezaları
- ikame matrisleri
Temel kuramlar
- Dinamik programlama ile global hizalama
- Needleman-Wunsch algoritması, dizgi ön eklerinin en iyi hizalama puanını veren dinamik programlama tablosunu doldurarak, iki dizinin uzunluklarının çarpımıyla orantılı bir sürede optimal bir uçtan uca (global) hizalama sağlamaktadır.
- Paylaşılan alt diziler için lokal hizalama
- Smith-Waterman algoritması, hizalamaların herhangi bir yerden başlayıp bitmesine izin vermek için tekrarlamayı değiştirmekte, en yüksek puanlı eşleşen bölgeyi (lokal hizalama) bulmaktadır; bu, aksi takdirde farklı diziler içindeki korunmuş fragmanları tespit etmek için temel bir öneme sahiptir.
Klinik önem
Dizi hizalama, hesaplamalı biyolojinin temel taşlarından biridir ve DNA, RNA ve protein dizilerini homoloji, evrimsel çıkarım ve veritabanı araması (sezgisel BLAST lokal hizalama üzerine kuruludur) için karşılaştırmada kullanılmaktadır. Biyoloji dışında, aynı düzenleme mesafesi mekanizması yazım denetimi, bulanık metin eşleştirme, sürüm kontrolü farkları ve konuşma ile el yazısı karşılaştırmalarını desteklemektedir.
Tarihçe
Levenshtein, düzenleme mesafesini 1965 yılında tanıtmıştır. Needleman ve Wunsch, proteinler için ilk dinamik programlama tabanlı global hizalama algoritmasını 1970'te sunmuş, Smith ve Waterman ise lokal hizalamayı 1981'de tanıtmıştır. Hirschberg'in doğrusal alan tekniği (1975) ve BLAST gibi daha sonraki sezgisel yöntemler, hizalamayı büyük ölçekli pratik kullanıma genişletmiştir.
Öne çıkan isimler
- Saul Needleman
- Christian Wunsch
- Temple Smith
- Michael Waterman
- Vladimir Levenshtein
İlgili konular
Temel eserler
- needleman1970
- smith1981
- gusfield1997
Sıkça sorulan sorular
- Global ve lokal hizalama arasındaki fark nedir?
- Global hizalama (Needleman-Wunsch), iki diziyi uçtan uca hizalamakta ve benzer uzunlukta olduklarında ve baştan sona ilişkili olmaları beklendiğinde uygun olmaktadır. Lokal hizalama (Smith-Waterman) ise en iyi eşleşen alt bölgeyi bulmakta ve dizilerin yalnızca belirli kısımları benzer olduğunda, örneğin daha büyük diziler içindeki korunmuş bir alan gibi durumlarda uygun görülmektedir.
- Dizi hizalama, en uzun ortak alt dizi ile aynı mıdır?
- Birbirleriyle yakından ilişkilidirler. En uzun ortak alt dizi, belirli bir puanlama (eşleşmeler ödüllendirilir, boşluklar serbesttir, eşleşmeyenler yasaktır) ile hizalamanın özel bir durumudur. Genel hizalama, ikame maliyetleri ve boşluk cezaları ile daha zengin bir puanlama kullanmaktadır, ancak her ikisi de aynı tür dinamik programlama tekrarlamasıyla çözülmektedir.