Reconstructing weighted phylogenetic trees and phylogenetic networks using answer set programming
Çözüm kümesi programlama kullanarak ağırlıklı filogenetik ağaçlar ve ağların çıkarımı
- Tez No: 309366
- Danışmanlar: YRD. DOÇ. DR. ESRA ERDEM
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 137
Özet
Türlerin tarihsel evrim ilişkileri filogenetik ağaç olarak modellenebilir. Buağacların yaprakları türleri, aradaki düğümleri ataları ve kenarları genetik ilişkileri temsil eder. Türler arasında ödünç alma olduğu durumda, filogenetikağaçlara bu tür ilişkileri gösteren az sayıda kenar eklenerek, filogenetik ağlaradönuştürülebilirler. Ancak verilen bir tür ailesi için oldukça fazla olası ağaçve ağ olabilir ve bu ağaçları otomatik olarak analiz edebilecek bir sistemmevcut değil. Bu tez, çözüm kümesi programlama (ASP) kullanarak ağırlıklıfilojeni ve filogenetik ağ hesaplamak amacıyla yeni hesaplama yöntemlerive yazılım sistemleri geliştirerek filogenetik çalışmalarındaki bu ihtiyacıkarşılamaktadır. Ağırlıklı filojeni hesaplamasının arkasındaki genel fikir, birfilojeninin ve filogenetik ağin ne kadar makul olduğunu gösteren bir ağırlıkfonksiyonu kullanarak belirli bir ağırlığın üzerindeki filojenileri ve filogenetikağları ASP çözücülerini kullanarak hesaplamak.Bu tez kapsamında, uyumluluk kriterine göre ağırlıklı filojeni ve filogenetikağaç çıkarımı ile ilgili hesaplama problemlerini inceledik, bu problemlerinhesaplama karmaşıklığını analiz ettik. Ağırlıklı filojenileri ve filogenetikağları hesaplamak için iki tip (gösterime dayalı ve aramaya dayalı) ASP'ye dayalı hesaplama yöntemi geliştirdik. Bu yöntemlerden yararlanarak,büyük veriler üzerinde filojeni çıkarımı yapmak için böl-ve-yönet yönteminedayanan yeni bir algoritma geliştirdik. Bu algoritmaya dayalı yazılım sistemlerigeliştirdik: ağırlıklı filojeni çıkarımı ve analizi yapan Phylo-ASP,ve ağırlıklı filogenetik ağ çıkarımı yapan PhyloNet-ASP. İki gerçek veriüzerinden (Hint Avrupa dilleri ve Türkiye'deki meşe ağaçları) yaptığımıztestler ile yöntemlerimizin ve yazılım sistemlerimizin etkinliğini gösterdik.Bunların yanında, yöntemlerimizi ASP'de ağırlıklı çözümler bulacak şekildegenelleştirdik ve bir ASP çözücüyü (clasp-w) bu yöntemlere uygun bir şekildedeğiştirerek birçok ASP uygulaması için yararlı bir araç sağladık.
Özet (Çeviri)
Evolutionary relationships between species can be modeled as a tree(called a phylogeny) whose nodes represent the species, internal vertices representtheir ancestors and edges represent genetic relationships. If there areborrowings between species, then a small number of edges that denote suchborrowings can be added to phylogenies turning them into (phylogenetic)networks. However, there are too many such trees/networks for a given familyof species but no phylogenetic system to automatically analyze them. Thisthesis fulfills this need in phylogenetics, by introducing novel computationalmethods and tools for computing weighted phylogenies/networks, using AnswerSet Programming (ASP). The main idea is to define a weight functionfor phylogenies/networks that characterizes their plausibility, and to reconstructphylogenies/networks whose weights are over a given threshold usingASP solvers.We have studied computational problems related to reconstructing weightedphylogenies/networks based on the compatibility criterion, analyzed theircomputational complexity, and introduced two sorts of ASP-based methods(representation-based and search-based) for computing weighted phyloiiigenies/networks. Utilizing these methods, we have introduced a novel divideand-conquer algorithm for computing large weighted phylogenies, and implementeda phylogenetic system (Phylo-ASP) based on it. We have alsoimplemented a phylogenetic system (PhyloNet-ASP) for reconstructingweighted networks. We have shown the applicability and the efectiveness ofour methods by performing experiments on two real datasets: Indo Europeanlanguages, and Quercus species in Turkey. Moreover, we have extended ourmethods to computing weighted solutions in ASP and modified an ASP solveraccordingly, providing a useful tool (clasp-w) for various ASP applications.
Benzer Tezler
- The Implementation of multi spin echo method for fast T2 weighted imaging in 0.15 tesla magnetic resonance imaging sistem
0.15 resla manyetik rezonans görüntüleme sisteminde çoklu spin yankı kullanarak hızlı T2 ağırlık görüntü alma
NEZİH AKPINAR
Yüksek Lisans
İngilizce
1997
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ZİYA İDER
- Deep image compression with a unified spatial and channel context auto-regressive model
Birleştirilmiş uzaysal ve kanal içerik özbağlanım modeli ile derin görüntü sıkıştırma
ALİ SEFKAN ULUDAĞ
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATİH KAMIŞLI
- Magnetic resonance electrical impedance tomography based on the solution of the convection equation and 3D Fourier transform-magnetic resonance current density imaging
Taşınım denkleminin çözümüne dayalı manyetik rezonans elektriksel empedans tomografi ve 3B Fourier dönüşümü-manyetik rezonans akım yoğunluğu görüntüleme
ÖMER FARUK ORAN
Yüksek Lisans
İngilizce
2011
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. YUSUF ZİYA İDER
- Yapay sinir ağlarına dayalı uçak algılayıcı arızası tespiti ve sistemin yeniden yapılandırılması
Aircraft sensor fault detection and system reconstruction based on artificial neural networks
UĞUR KILIÇ
Doktora
Türkçe
2021
Havacılık MühendisliğiEskişehir Teknik ÜniversitesiHavacılık Elektrik ve Elektroniği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜLAY ÜNAL
- Photometric stereo considering highlights and shadows
Parlama ve gölgeleri gözönüne alan fotometrik stereo
SONER BÜYÜKATALAY
Doktora
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. UĞUR HALICI
YRD. DOÇ. DR. ÖZLEM BİRGÜL