Novel techniques for protein structure characterization using graph representation of proteins

Abstract

Proteinler sonsuz sayıda farklı yapıda bulunabilirler. PDB veribanında, bu sonsuz olasılıklardan, 3 boyutlu yapısı belirlenmiş, elli binin üzerinde protein vardır. Proteinin 3 boyutlu yapısı onun fonksiyonu için önemlidir. Yapısı aynı olan protein ailelerinde bile protein uzunlukları ve aminoacid dizilişleri değişkenlik gösterir. Bu değişkenlik evrimin aminoacid dizilişlerine bir yansımasıdır. Protein yapılarının bilgileri graf temsili ile elde edilebilir. Protein ailelerinin yapı benzerlikleri graflar üzerinde hesaplanan yapı özellikleri yardımıyla bulunabilir. Bu yapı özelliklerinin bazıları, bir düğümün, komşu sayısı, ne kadar merkezi bir rol aldığı ve komşularının birbirlerini ne kadar tanıdığının ölçüsüdür.Bir çok protein karşılaştırma ve hizzalama metodları her bir atomun koordinatlarını kullanır ve bu koordinatların doğru olarak elde edilmiş olması önem taşır ve deneysel metodlarla bu verilere ulaşmak zahmetlidir. Bu metodlar bioinformatiğin bir çok alanında kullanılır. Bunların başlıcaları protein katlanma tayini, fonksiyon belirleme, domain tayini, ve katlanma sınıflamasıdır. Önerdiğimiz algoritmalar ile aynı sonuçlar daha az bilgi kullanılarak üretilebilir.Bu tez çalışmasında, proteinler graflar olarak temsil edilmiş ve graf özellikleri kullanılarak gerçek ve gerçek olmayan proteinlerin ayırt edilebilmesi için bir algoritma geliştirilmiştir. Bu algoritma neticesinde proteinlerin tümünün ve bölgesel hizzalama metodlari ile protein yapılarının karşılaştırılması sağlanmıştır. Bununla birlikte, bölgesel hizzalama algoritması ile protein fonksiyon tayini yapılmıştır ve alt graf eşleştirme metodu ile domain tayini yapılmıştır. Doğru katlanmayı bulabilmek için bir de genetic algoritma tabanlı bir uygulama geliştirilmiştir. Tüm metodlar ile doğruluk değerleri yüksek sonuçlar elde edilmiştir.

Proteins exhibit an infinite variety of structures. Around 50K 3D structures of proteins exist in PDB database among unlimited possibilities. The three dimensional structure of a protein is crucial to its function. Even within a common structure family, proteins vary in length, size, and sequence. This variation is the reflection of evolution on protein sequences. The intrinsic information in protein structures can be captured by their graph representations. The structural similarities between protein families can be deduced using their structural features such as connectivity, betweenness, and cliquishness.Most of the structure comparison and alignment methods use all atom coordinates that?s why they need reliable full atom representation of proteins which is difficult to obtain using experimental methods. These methods can be used for variety of problems in bioinformatics such as protein fold prediction, function annotation, domain prediction, and fold classification. Our approach can capture the same knowledge by using much less information from the actual structure.In this thesis, we used graph representations of proteins and graph theoretical properties to discriminate native and non-native proteins. Then we used these methods to find out overall and local similarity of protein structures by using dynamic programming. Afterward, local alignment using dynamic programming is used to determine the function of a protein. Moreover, sub graph matching algorithms was employed for domain prediction. In order to find the correct fold we also developed a genetic algorithm based threading approach. All these applications gave better or comparable results to state of the art.