Using Graphs to Relate Patient’s Clinical and Geographical Data.

The integration of clinical and geographical data of patients is a recent trend in bio and medical informatics since such integration may reveal hidden association association patterns among patients. For instance, the presence of the same disease or the pattern of changes in biological analytes in patients of the different geographical areas may suggest the presence of possible environmental factors that affect patients health. The joint analysis of patients considering both analytical parameters and geographical features requires the use of appropriate models and algorithms to integrate and mine such data. A possibility could be the use of the dual network model that has been used recently in bioinformatic to model many interesting biological scenarios. A dual network is a pair of related graph sharing a subset of nodes and edges. Usually one of the two graph is unweighted (a physical network representing physical association among nodes) while the other one is edge-weighted (a conceptual network representing conceptual association among nodes). In such a way related subset of nodes are connected in the physical network and the induced subgraph in the conceptual network has a high density. In such a model the the problem of finding the densest connected subgraph (DCS) which has the largest density in the conceptual network and is also connected in the physical network is relevant. In our approach we model patients as nodes in both networks, while the physical network models the geographical association among them (i.e. patients living in the same area or in areas with same environmental factors), while the conceptual network represents the association among patients considering similar patterns of biological analytes (for instance patients having a common mutation, or patients having a similar pattern of changes in analytes and the strenght of the association is represented by the weight of the nodes). Then we mine both networks searching for DCS. In our representation a DCS is a group of geographically related patients having a similar pattern of expression. The DCS problem is NP-hard, thus the need for the introduction of reliable solution arises. Here we formalize the problem and then we map the DCS problem in to a graph alignment problem. Then we propose a possible solution. Our findings are currently under the validation of the clinicians.