Weighted bipartite crossing minimization applications on biclustering and graph unions

Abstract

Çift taraflı kümeleme problemi, biyol ile ilgili verilerin alt matrisler arasından, belli oranda verinin, sütun kısmında ve satır kısmında ilintili olanları elde etme problemidir. Biz adı LEB(Localize-and-Extract Biclusters) olan bir yöntem sunarak, cift taraflı kümeleme problemini tüm veri üzerinde çalışması yerine, kendine yakın komşu olan alt matrisler üzerinde çalışmasını sağladık. Bu sayede tarama süreci, genelden, yerel alt kümelere indirgenmiş oldu. Yerelleştirme probleminin temelini, çizge tabanlı teorik yöntem kullanarak Çift taraflı Kümeleme problemi ile ilintili olduğunu deney yaparak belirledik. Yerelleştirme metodundan sonra bu küçük alt yapıların birleştirilmesi içinde ayrı yöntem önerdik. Son olarakta biz öne sürdüğümüz yöntemin performansını birçok deney yaparak hem gerçek hem de sanal veriler üzerinde denedik. Bunun yanısıra, çizgeler için öne sürdüğümüz yöntemi, Çizgelerin Görselleştirilmesi içinde kullandık. Bunu da ikinci kısımda ayrınıtılı olarak inceledik.

Biclustering gene expression data is the problem of extracting submatrices of genes and conditions exhibiting significant correlation across both the rows and the columns of a data matrix of expression values. We provide a method, LEB (Localize-and-Extract Biclusters) which reduces the search space into local neighborhoods within the matrix by first localizing correlated structures. The localization procedure takes its roots from effective use of graph-theoretical methods applied to problems exhibiting a similar structure to that of biclustering. Once interesting structures are localized the search space reduces to small neighborhoods and the biclusters are extracted from these localities. We evaluate the effectiveness of our method with extensive experiments both using artificial and real datasets. Finally, we also used our crossing minimization heuristics for graph visualization in a layered fashion.