Yazan : Şadi Evren ŞEKER

Bu yazının amacı, dizgi yaslaması (string alignment) kavramını açıklamaktır. Literatürde dizilim yaslaması (sequence alignment) olarak da geçen kavram basitçe iki dizgiyi alarak bu dizgilerin birbiri ile olan ilişkilerini bulmayı hedefler.

Günümüzde özellikle biyobilişim (bioinformatics) çalışmalarının artması ile, gen dizilimlerinin karşılşatırılması çalışmalarında önemli bir role sahip olmuştur.

Örneğin iki adet dizgi (string) aşağıdaki şekilde verilmiş olsun:

GCACGCTG

GACGCGCG

Amacımız bu dizgilerin birbiri ile olan yaslamasını (hizalamasını) bulmak. Buradaki kasıt, dizgilerden birisinin üzerine harf ekleme veya çıkarma işlemi yapılarak diğerine ulaşan en kısa yolu bulmaktır.

Örneğin bir dizgi hizalama algoritması olan Hunt-Macllory algoritmasına göre, yukarıdaki iki dizginin hizalanmış hali aşğaıdaki şekildedir:

GCACGCTG–

G-ACGC-GCG

Görüldüğü üzere ikinci ve yedincei harflerde ikinci dizgiden çıkarma yapılıdığı bulunmuş, buna karşılık dokuzuncu ve onunca harflerde de ilk dizgiden çıkarılma yapıldığı kabul edilmiştir.

Bu sayede iki dizgi birbirine göre hizalı hale getirilmiş olur. Aradaki eksik genler bulunarak hizalanır.

Ayrıca dizgi hizalama algoritmaları, dinamik programlama (dynamic programming) kullanımı açısından oldukça elverişlidir.

Dizgi hizalama algoritmaları, iki dizgiyi hizalamak ve eksik ve fazla harfleri bulmak için kullanılır ancak bu amaç, aşağıdaki bazı diğer amaçlara yardım eder:

  • En uzun ortak küme problemi (longest common subsequence problem) çözümü

  • İki dosya arasında intihal bulunması (pligiarism detection)

  • Bir dizgideki hataların bulunması ve düzeltilmesi (error detection , error correction)

  • Biyobilişim çalışmaları (bioinformatics)

  • Doğal dil işleme çalışmaları (natural language processing)

Aşağıda, dizgi hizalama algoritmalarından bazıları verilmiştir:


Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir