Weighted bipartite crossing minimization applications on biclustering and graph unions

Abstract

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 in to 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 biblustering. 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.

Ç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 çift 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. Yerleştirme problemimin temelini, çizge tabanlı teorik yöntem kullanarak çift taraflı kümeleme problemi ile ilintili olduğunu deney yaparak belirledik. Yerlleş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 hemde sanal veriler üzerinde denedik. Bunun yanısıra çizelgeler için öne sürdüğümüz yöntemi, çizelgeler için öne sürdüğümüz yöntemi, çizelgelerin görselleştirmesi içinde kullandık. Bunu da ikinci kısımda ayrıntılı olarak inceledik.