Integer linear programming based solutions for construction of biological networks

Abstract

Gen düzenleme veya sinyal ağlarının pertürbasyon deneyleri ve gen ifade incelemesiyle çıkarımı biyoenformatikteki zor problemlerden birisidir. Yakın zamanda, çıkarım problemi referans ağ biçimlendirmesi problemi olarak formüle edilmiş ve pertürbasyon deneyleriyle uyumlanması için referans ağ üzerinde gerçekleştirilen minimum biçimlendirme işlem sayısının bulunmasının NP-Tam bir problem olduğu gösterilmiştir. Bu doktora tezinde, biyolojik ağların yeniden yapılandırılması için doğrusal programlama tabanlı çözümler önerilmiştir. RNA engelleme (RNAi) verisi ve referans ağ kullanılarak, sinyal ağlarının yeniden yapılandırılması için tam sayılı doğrusal programlama (TDP) modeli geliştirilmiştir. TDP modeli optimal çözümü garanti etmektedir ancak hesaplama karmaşıklığından dolayı yalnızca 10-15 genden oluşan küçük ağlar için elverişlidir. Büyük ağları ölçeklendirmek için böl ve yönet tabanlı yeni bir yöntem önerilmiştir. Bu yöntemde verilen referans ağ, ayrı ayrı çözülen alt ağlara ayrılmakta ve bu çözümler büyük ağın çözümünü oluşturmak için birleştirilmektedir. Fakat RNAi verisini kullanarak sinyal ağlarının yeniden yapılandırılması için geliştirdiğimiz çözümler çoklu alıcı/hedef içeren ağlar için uygun değildir. Buna benzer ağların çözümü için gen ifade verisi kullanılmıştır ve yeni bir TDP tabanlı çizge teorik yöntem geliştirilmiştir. Önerilen yöntemler; gerçek, yari sentetik ve sentetik verilerle doğrulanmıştır ve literatürdeki yöntemlerle karşılaştırılması, önerilen yöntemlerin büyük ağlara ölçeklenmede benzer ya da daha iyi biyolojik doğruluk elde ettiğini göstermiştir.

Inference of gene regulatory or signaling networks from perturbation experiments and gene expression assays is one of the challenging problems in bioinformatics. Recently, the inference problem has been formulated as a reference network editing problem and it has been show that finding the minimum number of edit operations on a reference network in order to comply with perturbation experiments is an NP-complete problem. In this dissertation, we propose linear programming based solutions for reconstruction of biological networks. We propose an integer linear programming (ILP) model for reconstruction of signaling networks from RNAi data and a reference network. The ILP model guarantees the optimal solution; however, is practical only for small networks of size 10-15 genes due to computational complexity. In order to scale for large networks, we propose a divide and conquer based heuristic, in which a given reference network is divided into smaller sub-networks that are solved separately and the solutions are merged together to form the solution for the large network. However the solution that we have developed for reconstruction of signaling networks using RNA interference data is not suitable for networks with multiple sources and sinks. In order to handle such networks, we use gene expression data and develop another ILP based graph theoretical method. We validate our proposed approaches on real, semi-synthetic and synthetic data sets, and comparison with the state of the art shows that our proposed approaches are able to scale better for large networks while attaining similar or better biological accuracy.