Biomedical subjects

Jon Kleinberg

Publications and source records attributed to Jon Kleinberg.

4 recordsLinked to original sources

PubMed2004

Traffic-based feedback on the web.

Usage data at a high-traffic web site can expose information about external events and surges in popularity that may not be accessible solely from analyses of content and link structure. We consider sites that are organized around a set of items available for purchase or download, consider, for example, an e-commerce site or collection of online research papers, and we study a simple indicator of collective user interest in an item, the batting average, defined as the fraction of visits to an item's description that result in an acquisition of that item. We develop a stochastic model for identifying points in time at which an item's batting average experiences significant change. In experiments with usage data from the Internet Archive, we find that such changes often occur in an abrupt, discrete fashion, and that these changes can be closely aligned with events such as the highlighting of an item on the site or the appearance of a link from an active external referrer. In this way, analyzing the dynamics of item popularity at an active web site can help characterize the impact of a range of events taking place both on and off the site.

Biological Warfare↗

PubMed2004

Computational analysis of sequence selection mechanisms.

Mechanisms leading to gene variations are responsible for the diversity of species and are important components of the theory of evolution. One constraint on gene evolution is that of protein foldability; the three-dimensional shapes of proteins must be thermodynamically stable. We explore the impact of this constraint and calculate properties of foldable sequences using 3660 structures from the Protein Data Bank. We seek a selection function that receives sequences as input, and outputs survival probability based on sequence fitness to structure. We compute the number of sequences that match a particular protein structure with energy lower than the native sequence, the density of the number of sequences, the entropy, and the "selection" temperature. The mechanism of structure selection for sequences longer than 200 amino acids is approximately universal. For shorter sequences, it is not. We speculate on concrete evolutionary mechanisms that show this behavior.

Computer Simulation↗

PubMed2003

A graph-theoretic approach to comparing and integrating genetic, physical and sequence-based maps.

For many species, multiple maps are available, often constructed independently by different research groups using different sets of markers and different source material. Integration of these maps provides a higher density of markers and greater genome coverage than is possible using a single study. In this article, we describe a novel approach to comparing and integrating maps by using abstract graphs. A map is modeled as a directed graph in which nodes represent mapped markers and edges define the order of adjacent markers. Independently constructed graphs representing corresponding maps from different studies are merged on the basis of their common loci. Absence of a path between two nodes indicates that their order is undetermined. A cycle indicates inconsistency among the mapping studies with regard to the order of the loci involved. The integrated graph thus produced represents a complete picture of all of the mapping studies that comprise it, including all of the ambiguities and inconsistencies among them. The objective of this representation is to guide additional research aimed at interpreting these ambiguities and inconsistencies in locus order rather than presenting a "consensus order" that ignores these problems.

Chromosome Mapping↗

PubMed2002

Constructing comparative genome maps with unresolved marker order.

Comparative genome maps are a powerful tool for interpreting the genomes of related organisms. The species maps which are the input to the process of constructing comparative maps are often themselves constructed from incomplete or inconsistent data, resulting in markers (or genes) whose order is not fully resolved. This incomplete marker order information is often handled by placing markers whose relative order cannot be reliably inferred together in a bin which is mapped to a common location. Previous automated and manual methods have handled such markers in an ad hoc or arbitrary way. We present efficient algorithms for comparative map construction that provide a principled method for handling unresolved marker order. The algorithms are based on a technique for efficiently computing a marker order that optimizes a natural parsimony criterion; in this way, they also yield a working hypothesis about the original incomplete data set.

Algorithms↗