We present a novel and efficient algorithm, Path Covering, for solving the most reliable subgraph problem. A reliable subgraph gives a concise summary of the connectivity between two given individuals in a social network. Formally, the given network is seen as a Bernoulli random graph Q, and the objective is to find a subgraph H ⊂ Q with at most B edges such that the probability that a path exists in H between the given two individuals is maximized. The algorithm is based on an efficient stochastic search of candidate paths, and the use of Monte-Carlo simulation to cast the problem as a set cover problem. Experimental evaluation on real graphs derived from DBLP bibliography database indicates superior performance of the proposed algorithm.

We describe TreeDT, a novel association-based gene mapping method. Given a set of disease-associated haplotypes and a set of control haplotypes, TreeDT predicts likely locations of a disease susceptibility gene. TreeDT extracts, essentially in the form of haplotype trees, information about historical recombinations in the population: A haplotype tree constructed at a given chromosomal location is an estimate of the genealogy of the haplotypes. TreeDT constructs these trees for all locations on the given haplotypes and performs a novel disequilibrium test on each tree: Is there a small set of subtrees with relatively high proportions of disease-associated chromosomes, suggesting shared genetic history for those and a likely disease gene location? We give a detailed description of TreeDT and the tree disequilibrium tests, we analyze the algorithm formally, and we evaluate its performance experimentally on both simulated and real data sets. Experimental results demonstrate that TreeDT has high accuracy on difficult mapping tasks and comparisons to other methods (EATDT, HPM, TDT) show that TreeDT is very competitive.

We introduce and evaluate TreeDT, a novel gene mapping method which is based on discovering and assessing tree-like patterns in genetic marker data. Gene mapping aims at discovering a statistical connection from a particular disease or trait to a narrow region in the genome. In a typical case-control setting, data consists of genetic markers typed for a set of disease-associated chromosomes and a set of control chromosomes. A computer scientist would view this data as a set of strings.TreeDT extracts, essentially in the form of substrings and prefix trees, information about the historical recombinations in the population. This information is used to locate fragments potentially inherited from a common diseased founder, and to map the disease gene into the most likely such fragment. The method measures for each chromosomal location the disequilibrium of the prefix tree of marker strings starting from the location, to assess the distribution of disease-associated chromosomes.We evaluate experimentally the performance of TreeDT on realistic, simulated data sets, and comparisons to state of the art methods (TDT, HPM) show that TreeDT is very competitive.

Genetic markers are being increasingly utilized in gene mapping. The discovery of associations between markers and patient phenotypes - such as a disease status - enables the identification of potential disease gene loci. The rationale is that, in diseases with a reasonable genetic contribution, diseased individuals are more likely to have associated marker alleles near the disease susceptibility gene than control individuals. We describe a new gene mapping method-haplotype pattern mining (HPM) - that is based on discovering recurrent marker patterns. We define a class of useful haplotype patterns in genetic case-control data, give an algorithm for finding disease-associated haplotypes, and show how to use them to identify disease susceptibility loci. Experimental studies show that the method has good localization power in data sets with large degrees of phenocopies and with lots of missing and erroneous data. We also demonstrate how the method can be used to discover several genes simultaneously.