# Graph theoretical approach to compare n pair of variables along a set of interval

I am dealing a bioinformatics problem and need help in approaching it in the right direction.

I have a set of variables that represent different kinds of genomic data and are real valued. I am trying to compare all these different variables among two species (though in the future I might be interested in generalizations to more than 2 species). What I need to do is to develop a graph theoretical method to calculate an entropy measure (or a better evolutionary distance measure) among all different genomic interval and cluster the pairs according to a high/low entropy measure.

So in genomics in the case of multiple species/two species there would be genomic regions which have a similar DNA sequence (known as orthologus regions). These regions would have a epigenetic/epigenomic mark associated with them. Such marks generally affect the gene expression/the overall chromatin make up of the genome or chromosome. What I want to do is identify regions of orthologus DNA which have high evolutionary conservation and high epigenomic conservation. I also want to identify regions of DNA between 2 or multiple species which have high evolutionary and epigenomic conservation or low evolutionary conservation and high epigenomic conservation and vice versa. What I want to do at the end is to develop a method that would help ,make multi-species /pairwise comparison at the end. Since I am not a formally trained Computer Scientist I don't know what would be a good approach/algorithm to use.

PS: epigenomic data would generally be in the form of counts (normalized to RPKM (https://wiki.nci.nih.gov/pages/viewpage.action;jsessionid=5265E39473A073390CF868D3E56E619A?pageId=71439191). While RPKM of epigenomic signals is available for a span of regions (say 200 base pairs) the evolutionary conservation data is available for every base of DNA (the evolutionary conservation value of a base lies between 0 and 1)

• It's not clear to me what you are looking for. What do you mean by "different genomic interval"? What pairs do you want to cluster? What entropy measure do you want to use, or what properties do you want it to have? Why do you think it should be a graph-theoretic method specifically, as opposed to some other measure? Can you edit the question to clarify these points? If you're interested in clustering, there are many resources on clustering; have you read the Wikipedia article? Read books on clustering? – D.W. Feb 29 '16 at 7:17
• Hi I have added some more information at the top. Let me know if that helps make things clear. – Saad Khan Mar 2 '16 at 20:16
• This is not really a computer science question, since you are asking for a statistical model (a way of identifying your orthologus regions). Once you have a statistical model, the computer science question would be how to apply it efficiently. – Yuval Filmus Mar 2 '16 at 21:24
• Actually orthologus regions are already identified but what we are doing here is to differentiate them on the basis of their epigenomic marks. So we do need a more efficient statistical way to do that/a computer science solution for that. – Saad Khan Mar 3 '16 at 20:46
• Personally, I can't understand the CS problem. I appreciate the edits, but I'm overwhelmed by biological terms that I don't understand. Superficially, it sounds to me like a Stats question where you are asking for a statistical model, not a CS question. A CS question would be if you could present a well-defined algorithmic task (e.g., given this statistical model, how do I efficiently compute the likelihood of the data, or something like that). So, I'm struggling to find a CS question here. Any community votes? – D.W. Mar 3 '16 at 22:46