901722
Dynamic programming algorithms for haplotype block partitioning: applications to human chromosome 21 haplotype data
Recent studies have shown that the human genome has a haplotype block structure such that it can be divided into discrete blocks of limited haplotype diversity. Patil et al. [6] and Zhang et al. [12] developed algorithms to partition haplotypes into blocks with minimum number of tag SNPs for the entire chromosome. However, it is not clear how to partition haplotypes into blocks with restricted number of SNPs when only limited resources are available. In this paper, we first formulated this problem as finding a block partition with a fixed number of tag SNPs that can cover the maximal percentage of a genome. Then we solved it by two dynamic programming algorithms, which are fairly flexible to take into account the knowledge of functional polymorphism. We applied our algorithms to the published SNP data of human chromosome 21 combining with the functional information of these SNPs and demonstrated the effectiveness of them. Statistical investigation of the relationship between the starting points of a block partition and the coding and non-coding regions illuminated that the SNPs at these starting points are not significantly enriched in coding regions. We also developed an efficient algorithm to find all possible long local maximal haplotypes across a subset of samples. After applying this algorithm to the human chromosome 21 haplotype data, we found that samples with long local haplotypes are not necessarily globally similar.
11712321
HAPLORE: a program for haplotype reconstruction in general pedigrees without recombination
MOTIVATION
Haplotype reconstruction is an essential step in genetic linkage and association studies. Although many methods have been developed to estimate haplotype frequencies and reconstruct haplotypes for a sample of unrelated individuals, haplotype reconstruction in large pedigrees with a large number of genetic markers remains a challenging problem.


METHODS
We have developed an efficient computer program, HAPLORE (HAPLOtype REconstruction), to identify all haplotype sets that are compatible with the observed genotypes in a pedigree for tightly linked genetic markers. HAPLORE consists of three steps that can serve different needs in applications. In the first step, a set of logic rules is used to reduce the number of compatible haplotypes of each individual in the pedigree as much as possible. After this step, the haplotypes of all individuals in the pedigree can be completely or partially determined. These logic rules are applicable to completely linked markers and they can be used to impute missing data and check genotyping errors. In the second step, a haplotype-elimination algorithm similar to the genotype-elimination algorithms used in linkage analysis is applied to delete incompatible haplotypes derived from the first step. All superfluous haplotypes of the pedigree members will be excluded after this step. In the third step, the expectation-maximization (EM) algorithm combined with the partition and ligation technique is used to estimate haplotype frequencies based on the inferred haplotype configurations through the first two steps. Only compatible haplotype configurations with haplotypes having frequencies greater than a threshold are retained.


RESULTS
We test the effectiveness and the efficiency of HAPLORE using both simulated and real datasets. Our results show that, the rule-based algorithm is very efficient for completely genotyped pedigree. In this case, almost all of the families have one unique haplotype configuration. In the presence of missing data, the number of compatible haplotypes can be substantially reduced by HAPLORE, and the program will provide all possible haplotype configurations of a pedigree under different circumstances, if such multiple configurations exist. These inferred haplotype configurations, as well as the haplotype frequencies estimated by the EM algorithm, can be used in genetic linkage and association studies.


AVAILABILITY
The program can be downloaded from http://bioinformatics.med.yale.edu.
6145819
HapBlock: haplotype block partitioning and tag SNP selection software using a set of dynamic programming algorithms
UNLABELLED
Recent studies have revealed that linkage disequilibrium (LD) patterns vary across the human genome with some regions of high LD interspersed with regions of low LD. Such LD patterns make it possible to select a set of single nucleotide polymorphism (SNPs; tag SNPs) for genome-wide association studies. We have developed a suite of computer programs to analyze the block-like LD patterns and to select the corresponding tag SNPs. Compared to other programs for haplotype block partitioning and tag SNP selection, our program has several notable features. First, the dynamic programming algorithms implemented are guaranteed to find the block partition with minimum number of tag SNPs for the given criteria of blocks and tag SNPs. Second, both haplotype data and genotype data from unrelated individuals and/or from general pedigrees can be analyzed. Third, several existing measures/criteria for haplotype block partitioning and tag SNP selection have been implemented in the program. Finally, the programs provide flexibility to include specific SNPs (e.g. non-synonymous SNPs) as tag SNPs.


AVAILABILITY
The HapBlock program and its supplemental documents can be downloaded from the website http://www.cmb.usc.edu/~msms/HapBlock.
31567164
Prediction of protein function using protein-protein interaction data
Assigning functions to novel proteins is one of the most important problems in the post-genomic era. We develop a novel approach that applies the theory of Markov random fields to infer a protein's functions using protein-protein interaction data and the functional annotations of its interaction protein partners. For each function of interest and a protein, we predict the probability that the protein has that function using Bayesian approaches. Unlike in other available approaches for protein annotation where a protein has or does not have a function of interest, we give a probability for having the function. This probability indicates how confident we are about the prediction. We apply our method to predict cellular functions (43 categories including a category "others") for yeast proteins defined in the Yeast Proteome Database, using the protein-protein interaction data from the Munich Information Center for Protein Sequences. We show that our approach outperforms other available methods for function prediction based on protein interaction data.
14716028
New Upper Bounds for Ramsey Numbers
The Ramsey numberR(G1,G2) is the smallest integerpsuch that for any graphGonpvertices eitherGcontainsG1orGcontainsG2, whereGdenotes the complement ofG. LetR(m,n)=R(Km,Kn). Some new upper bound formulas are obtained forR(G1,G2andR(m,n), and we derive some new upper bounds for Ramsey numbers here.
16504753
Minimizing downtime in seamless migrations of mobile applications
Application migration is a key enabling technology component of mobile computing that allows rich semantics involving location awareness, trust and timeliness of information processing by moving the application where the data is. Seamlessness is one of the key properties of mobile computing and downtime must be eliminated/minimized during the migration to achieve seamlessness. But migration involves large overheads, dominant of which are the overheads due to serialization and de-serialization [1]. To achieve seamless migration, an application state could be pre-serialized during the program's execution, and upon migration, the serialized data could be transmitted and de-serialized to get the execution started. Previous approach to this problem [1] removed dead state but still suffered from large migration overheads due to serialization on-demand that could lead to an unacceptable downtime.In this work, we develop a static compiler analysis plus runtime assisted framework to decrease the migration overhead to almost zero while minimizing the degradation in the program's performance. We achieve such a goal by deciding which data to be pre-serialized through analysis, and pre-serializing the state in the program. A safe state is kept that would allow immediate migration upon the arrival of an interrupt while minimizing frequent pre-serialization. When the migration interrupt comes in, the serialized data can be transmitted directly to the destination machine. This allows an application to resume its execution at the destination machine with almost no interruption (only a small amount of non-serialized data needs to be serialized during migration). The optimization serializes the data in such a way that a maximal number of functions can execute without interruption after migration. Our experiments with multimedia applications show that the migration latency is significantly reduced leading to a small downtime. Thus, the contribution of the paper is to provide an efficient methodology to perform seamless migration while limiting the overhead.
17536436
Combining visual and automated data mining for near-real-time anomaly detection and analysis in BGP
The security of Internet routing is a major concern because attacks and errors can result in data packets not reaching their intended destination and/or falling into the wrong hands. A key step in improving routing security is to analyze and understand it. In the past, we and other researchers have presented various visual-based, statistical-based, and signature-based methods of analyzing Internet routing data.
 In this paper, we describe an integration of visual and automated data mining methods for discovering and investigating anomalies in Internet routing. We show how these different components are combined in such a way as to complement each other, creating a very effective and useful analysis tool. In addition to performing analysis on archived data, our system is able to collect, process and visualize data in near-real-time.
7869643
Fast parallel algorithms for the unit cost editing distance between trees
We present three algorithms to find the distance. The first algorithm is a simple dynamic programming algorithm based on a postorder traversal whose complexity improves upon the best previously published algorithm due to Tai (T79 in JACM). The second and third algorithms are parallel algorithms based on the application of suffix trees to the comparison problem. The cost of executing these algorithms is a monotonic increasing function of the distance between the two trees. Results Let trees T I and T2 have numbers of levels L i and L 2 respectively. Let k be the actual distance between T 1 and T2. Let N be rain (IT11, IT2 ]). The asymptotic running times (assuming a concurrentread concurrent-write parallel random access machine) are:
52799334
On the Editing Distance Between Undirected Acyclic Graphs
We consider the problem of comparing CUAL graphs (Connected, Undirected, Acyclic graphs with nodes being Labeled). This problem is motivated by the study of information retrieval for bio-chemical and molecular databases. Suppose we define the distance between two CUAL graphs G1 and G2 to be the weighted number of edit operations (insert node, delete node and relabel node) to transform G1 to G2. By reduction from exact cover by 3-sets, one can show that finding the distance between two CUAL graphs is NP-complete. In view of the hardness of the problem, we propose a constrained distance metric, called the degree-2 distance, by requiring that any node to be inserted (deleted) have no more than 2 neighbors. With this metric, we present an efficient algorithm to solve the problem. The algorithm runs in time O(N1N2D2) for general weighting edit operations and in time for integral weighting edit operations, where Ni, i=1, 2, is the number of nodes in Gi, D=min{d1, d2} and di is the maximum degree of Gi.