CiteULike: AbnerCYH's library [706 articles]

A General Approximation Technique for Constrained Forest Problems

Michel Goemans — 2008-07-25T17:38:42-00:00

SIAM Journal on Computing, Vol. 24, No. 2. (1995), pp. 296-317.

Market Equilibrium via a Primal-Dual-Type Algorithm

Nikhil Devanur — 2008-07-24T04:40:27-00:00

(2002), pp. 389-395.

Link mining applications: progress and challenges

Ted Senator — 2006-05-01T15:44:36-00:00

SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 76-83.

Link mining: a survey

Lise Getoor — 2006-05-01T15:42:29-00:00

SIGKDD Explor. Newsl., Vol. 7, No. 2. (December 2005), pp. 3-12.

Link Analysis, Eigenvectors and Stability

Andrew Ng — 2006-03-13T13:00:34-00:00

(2001), pp. 903-910.

The HITS and the PageRank algorithms are eigenvector methods for identifying "authoritative" or "influential" articles, given hyperlink or citation information. That such algorithms should give consistent answers is surely a desideratum, and in this paper, we address the question of when they can be expected to give stable rankings under small perturbations to the hyperlink patterns. Using tools from matrix perturbation theory and Markov chain theory, we provide conditions under which...

Link Analysis Ranking Algorithms Theory And Experiments

Allan Borodin — 2005-10-11T18:13:20-00:00

The explosive growth and the widespread accessibility of the Web has led to surge of research activity in the area of information retrieval on the World Wide Web. The seminal papers of Kleinberg [31], and Brin and Page [9] introduced Link Analysis Ranking, where hyperlink structures are used to determine the relative authority of a Web page, and produce improved algorithms for the ranking of Web search results. In this paper we work within the hubs and authorities framework defined by...

On the Best Case of Heapsort

B Bollobás — 2008-07-22T05:11:42-00:00

Journal of Algorithms, Vol. 20, No. 2. (March 1996), pp. 205-217.

Although discovered some 30 years ago, the Heapsort algorithm is still not completely understood. Here we investigate thebest caseof Heapsort. Contrary to claims made by some authors that its time complexity isO(n), i.e., linear in the number of items, we prove that it is actuallyO(nlogn) and is, in fact, approximately half that of the worst case. Our proof contains a construction for an asymptotically best-case heap. In addition, the proof and construction provide theworst-casetime complexity and an asymptotically worst-case example forBottom-upversions of Heapsort.

Semantic integration to identify overlapping functional modules in protein interaction networks

Young-Rae Cho — 2007-07-25T05:48:46-00:00

BMC Bioinformatics, Vol. 8 (24 July 2007), 265.

Molecular interaction maps of bioregulatory networks: a general rubric for systems biology.

KW Kohn — 2006-01-30T13:34:11-00:00

Mol Biol Cell, Vol. 17, No. 1. (January 2006), pp. 1-13.

A standard for bioregulatory network diagrams is urgently needed in the same way that circuit diagrams are needed in electronics. Several graphical notations have been proposed, but none has become standard. We have prepared many detailed bioregulatory network diagrams using the molecular interaction map (MIM) notation, and we now feel confident that it is suitable as a standard. Here, we describe the MIM notation formally and discuss its merits relative to alternative proposals. We show by simple examples how to denote all of the molecular interactions commonly found in bioregulatory networks. There are two forms of MIM diagrams. "Heuristic" MIMs present the repertoire of interactions possible for molecules that are colocalized in time and place. "Explicit" MIMs define particular models (derived from heuristic MIMs) for computer simulation. We show also how pathways or processes can be highlighted on a canonical heuristic MIM. Drawing a MIM diagram, adhering to the rules of notation, imposes a logical discipline that sharpens one's understanding of the structure and function of a network.

Decomposition of overlapping protein complexes: A graph theoretical method for analyzing static and dynamic protein associations

Elena Zotenko — 2006-05-30T18:21:44-00:00

Algorithms for Molecular Biology, Vol. 1, No. 1. (26 April 2006), 7.

BACKGROUND:Most cellular processes are carried out by multi-protein complexes, groups of proteins that bind together to perform a specific task. Some proteins form stable complexes, while other proteins form transient associations and are part of several complexes at different stages of a cellular process. A better understanding of this higher-order organization of proteins into overlapping complexes is an important step towards unveiling functional and evolutionary mechanisms behind biological networks.RESULTS:We propose a new method for identifying and representing overlapping protein complexes (or larger units called functional groups) within a protein interaction network. We develop a graph-theoretical framework that enables automatic construction of such representation. We illustrate the effectiveness of our method by applying it to TNF-alpha/NF-kappaB and pheromone signaling pathways. CONCLUSIONS:The proposed representation helps in understanding the transitions between functional groups and allows for tracking a protein's path through a cascade of functional groups. Therefore, depending on the nature of the network, our representation is capable of elucidating temporal relations between functional groups. Our results show that the proposed method opens a new avenue for the analysis of protein interaction networks.

Charting protein complexes, signaling pathways, and networks in the immune system

Bauch — 2006-03-28T13:03:25-00:00

Immunological Reviews, Vol. 210, No. 1. (April 2006), pp. 187-207.

Evaluation of clustering algorithms for protein-protein interaction networks

Sylvain Brohee — 2006-11-06T23:08:06-00:00

BMC Bioinformatics, Vol. 7 (06 November 2006), 488.

Iterative Cluster Analysis of Protein Interaction Data

Vicente Arnau — 2005-01-29T20:31:28-00:00

Bioinformatics, Vol. 21, No. 3. (01 February 2005), 364.

Discovery of biological networks from diverse functional genomic data.

CL Myers — 2008-03-28T20:41:18-00:00

Genome Biol, Vol. 6, No. 13. (2005)

We have developed a general probabilistic system for query-based discovery of pathway-specific networks through integration of diverse genome-wide data. This framework was validated by accurately recovering known networks for 31 biological processes in Saccharomyces cerevisiae and experimentally verifying predictions for the process of chromosomal segregation. Our system, bioPIXIE, a public, comprehensive system for integration, analysis, and visualization of biological network predictions for S. cerevisiae, is freely accessible over the worldwide web.

On the complexity of deriving position specific score matrices from positive and negative sequences

Tatsuya Akutsu — 2008-07-19T08:17:33-00:00

Discrete Applied Mathematics, Vol. 155, No. 6-7. (1 April 2007), pp. 676-685.

Position-specific score matrices (PSSMs) have been applied to various problems in computational molecular biology. In this paper, we study the following problem: given positive examples (sequences) and negative examples (sequences), find a PSSM which correctly discriminates between positive and negative examples. We prove that this problem is solved in polynomial time if the size of a PSSM is bounded by a constant. On the other hand, we prove that this problem is NP-hard if the size is not bounded. We also prove hardness results for deriving multiple PSSMs and related problems.

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

Marc Tedder — 2008-07-18T17:42:46-00:00

Automata, Languages and Programming (2008), pp. 634-645.

Modular decomposition is fundamental for many important problems in algorithmic graph theory including transitive orientation, the recognition of several classes of graphs, and certain combinatorial optimization problems. Accordingly, there has been a drive towards a practical, linear-time algorithm for the problem. This paper posits such an algorithm; we present a linear-time modular decomposition algorithm that proceeds in four straightforward steps. This is achieved by introducing the notion of factorizing permutations to an earlier recursive approach. The only data structure used is an ordered list of trees, and each of the four steps amounts to simple traversals of these trees. Previous algorithms were either exceedingly complicated or resorted to impractical data-structures.

Unraveling Protein Networks with Power Graph Analysis

Loïc Royer — 2008-07-11T23:03:28-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000108.

Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks. We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution, indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein interactions, regulatory networks, or homology networks.

Encyclopedia of Algorithms

2008-07-16T13:37:20-00:00

(03 July 2008)

The Encyclopedia of Algorithms will provide a comprehensive set of solutions to important algorithmic problems for students and researchers interested in quickly locating useful information. The first edition of the reference will focus on high-impact solutions from the most recent decade; later editions will widen the scope of the work. Nearly 500 entries will be organized alphabetically by problem, with subentries allowing for distinct solutions and special cases to be listed by the year. An entry will include: * a description of the basic algorithmic problem * the input and output specifications * the key results * examples of applications * citations to the key literature Open problems, links to downloadable code, experimental results, data sets, and illustrations may be provided. All entries will be written by experts; links to Internet sites that outline their research work will also be provided. The entries will be peer-reviewed. This defining reference will be published in print and on line. The print publication will include an index of subjects and authors as well as a chronology for locating recent solutions. The online edition will supplement this index with hyperlinks as well as include hyperlinks in the text of the entries to related entries, xRefer citations, and other useful URLs mentioned above.

Modular decomposition of protein-protein interaction networks.

J Gagneur — 2006-08-18T17:19:04-00:00

Genome Biol, Vol. 5, No. 8. (2004)

We introduce an algorithmic method, termed modular decomposition, that defines the organization of protein-interaction networks as a hierarchy of nested modules. Modular decomposition derives the logical rules of how to combine proteins into the actual functional complexes by identifying groups of proteins acting as a single unit (sub-complexes) and those that can be alternatively exchanged in a set of similar complexes. The method is applied to experimental data on the pro-inflammatory tumor necrosis factor-alpha (TNF-alpha)/NFkappaB transcription factor pathway.

An optimal algorithm for checking regularity: (extended abstract)

Y Kohayakawa — 2008-07-10T16:00:22-00:00

(2002), pp. 277-286.

The algorithmic aspects of the regularity lemma

N Alon — 2008-07-08T11:35:09-00:00

Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on (1992), pp. 473-481.

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an <e1>n</e1>-vertex graph, can be found in time <e1>O</e1>(<e1>M</e1>(<e1>n</e1>)), where <e1>M</e1>(<e1>n</e1>)=O(<e1>n</e1><sup>2.376</sup>) is the time needed to multiply two <e1>n</e1> by <e1>n</e1> matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in <e1>NC</e1><sup>1</sup>

Small subsets inherit sparse $ε$-regularity

Stefanie Gerke — 2008-07-06T18:26:08-00:00

J. Comb. Theory Ser. B, Vol. 97, No. 1. (January 2007), pp. 34-56.

The Turán Theorem for Random Graphs

Yoshiharu Kohayakawa — 2008-07-06T18:26:07-00:00

Comb. Probab. Comput., Vol. 13, No. 1. (January 2004), pp. 61-91.

Regular pairs in sparse random graphs I

Y Kohayakawa — 2008-07-06T18:26:04-00:00

Random Struct. Algorithms, Vol. 22, No. 4. (July 2003), pp. 359-434.

The Blow-up Lemma

János Komlós — 2008-07-06T18:23:29-00:00

Comb. Probab. Comput., Vol. 8, No. 1-2. (1999), pp. 161-176.

Hypergraphs, quasi-randomness, and conditions for regularity

Yoshiharu Kohayakawa — 2008-07-06T18:23:26-00:00

J. Comb. Theory Ser. A, Vol. 97, No. 2. (February 2002), pp. 307-352.

Fast monte-carlo algorithms for finding low-rank approximations

Alan Frieze — 2008-07-06T18:23:24-00:00

J. ACM, Vol. 51, No. 6. (November 2004), pp. 1025-1041.

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems

Béla Csaba — 2008-07-06T18:23:19-00:00

(2002), pp. 74-83.

Property testing in hypergraphs and the removal lemma

V Rödl — 2008-07-06T18:23:14-00:00

(2007), pp. 488-495.

Integer and fractional packings of hypergraphs

V Rödl — 2008-07-06T18:22:10-00:00

Journal of Combinatorial Theory, Series B, Vol. 97, No. 2. (March 2007), pp. 245-268.

Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number of a k-uniform hypergraph is an NP-hard problem. Finding the fractional F0-packing number however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number in terms of and show that .

Testing versus estimation of graph properties

Eldar Fischer — 2008-07-06T18:22:13-00:00

(2005), pp. 138-146.

Cluster analysis for gene expression data: a survey

Daxin Jiang — 2006-05-06T21:00:31-00:00

Knowledge and Data Engineering, IEEE Transactions on, Vol. 16, No. 11. (2004), pp. 1370-1386.

DNA microarray technology has now made it possible to simultaneously monitor the expression levels of thousands of genes during important biological processes and across collections of related samples. Elucidating the patterns hidden in gene expression data offers a tremendous opportunity for an enhanced understanding of functional genomics. However, the large number of genes and the complexity of biological networks greatly increases the challenges of comprehending and interpreting the resulting mass of data, which often consists of millions of measurements. A first step toward addressing this challenge is the use of clustering techniques, which is essential in the data mining process to reveal natural structures and identify interesting patterns in the underlying data. Cluster analysis seeks to partition a given data set into groups based on specified features so that the data points within a group are more similar to each other than the points in different groups. A very rich literature on cluster analysis has developed over the past three decades. Many conventional clustering algorithms have been adapted or directly applied to gene expression data, and also new algorithms have recently been proposed specifically aiming at gene expression data. These clustering algorithms have been proven useful for identifying biologically relevant groups of genes and samples. In this paper, we first briefly introduce the concepts of microarray technology and discuss the basic elements of clustering on gene expression data. In particular, we divide cluster analysis for gene expression data into three categories. Then, we present specific challenges pertinent to each clustering category and introduce several representative approaches. We also discuss the problem of cluster validation in three aspects and review various methods to assess the quality and reliability of clustering results. Finally, we conclude this paper and suggest the promising trends in this field.

An introduction to variable and feature selection

Isabelle Guyon — 2005-04-22T17:16:32-00:00

J. Mach. Learn. Res., Vol. 3 (2003), pp. 1157-1182.

Data clustering: a review

AK Jain — 2005-01-26T09:13:11-00:00

ACM Comput. Surv., Vol. 31, No. 3. (September 1999), pp. 264-323.

The algorithmic aspects of the regularity lemma

N Alon — 2005-11-29T18:50:00-00:00

J. Algorithms, Vol. 16, No. 1. (January 1994), pp. 80-109.

The regularity lemma and approximation schemes for dense problems

A Frieze — 2008-07-05T13:09:44-00:00

(1996)

Property testing and its connection to learning and approximation

Oded Goldreich — 2008-07-05T13:09:40-00:00

J. ACM, Vol. 45, No. 4. (July 1998), pp. 653-750.

On characterizing hypergraph regularity

Y Dementieva — 2008-07-05T13:09:06-00:00

Random Struct. Algorithms, Vol. 21, No. 3-4. (2002), pp. 293-335.

An optimal algorithm for checking regularity: (extended abstract)

Y Kohayakawa — 2008-07-05T13:08:43-00:00

(2002), pp. 277-286.

Hardness of fully dense problems

Nir Ailon — 2008-07-05T13:08:01-00:00

Inf. Comput., Vol. 205, No. 8. (August 2007), pp. 1117-1129.

On minimum -connected k -dominating set problem in unit disc graphs

Weiping Shang — 2008-07-05T07:08:34-00:00

Journal of Combinatorial Optimization, Vol. 16, No. 2. (2008), pp. 99-106.

Abstract Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.

The Computational Complexity of Link Building

Martin Olsen — 2008-07-04T10:55:29-00:00

Computing and Combinatorics (2008), pp. 119-129.

We study the problem of adding k new links to a directed graph G(V, E) in order to maximize the minimum PageRank value for a given subset of the nodes. We show that this problem is NP-hard if k is part of the input. We present a simple and efficient randomized algorithm for the simple case where the objective is to compute one new link pointing to a given node t producing the maximum increase in the PageRank value for t. The algorithm computes an approximation of the PageRank value for t in G(V, E ∪ (v, t)) for all nodes v with a running time corresponding to a small and constant number of PageRank computations.

Quasi-bicliques: Complexity and Binding Pairs

Xiaowen Liu — 2008-07-04T09:43:14-00:00

Computing and Combinatorics (2008), pp. 255-264.

Protein-protein interactions (PPIs) are one of the most important mechanisms in cellular processes. To model protein interaction sites, recent studies have suggested to find interacting protein group pairs from large PPI networks at the first step, and then to search conserved motifs within the protein groups to form interacting motif pairs. To consider noise effect and incompleteness of biological data, we propose to use quasi-bicliques for finding interacting protein group pairs. We investigate two new problems which arise from finding interacting protein group pairs: the maximum vertex quasi-biclique problem and the maximum balanced quasi-biclique problem. We prove that both problems are NP-hard. This is a surprising result as the widely known maximum vertex biclique problem is polynomial time solvable [16]. We then propose a heuristic algorithm which uses the greedy method to find the quasi-bicliques from PPI networks. Our experiment results on real data show that this algorithm has a better performance than a benchmark algorithm for identifying highly matched BLOCKS and PRINTS motifs.

Spreading Messages

Ching-Lueh Chang — 2008-07-04T09:41:20-00:00

Computing and Combinatorics (2008), pp. 587-599.

We model a network in which messages spread by a simple directed graph G = (V,E) [8] and a function α: V→ℕ mapping each v ∈ V to a positive integer less than or equal to the indegree of v. The graph G represents the individuals in the network and the communication channels between them. An individual v ∈ V will be convinced of a message when at least α(v) of its in-neighbors are convinced. Suppose we are to convince a message to all individuals by convincing a subset S ⊆ V of individuals at the beginning and then let the message spread. We study minimum-sized sets S needed to convince all individuals at the end. In particular, our results include a lower bound on the size of a minimum S and the NP-completeness of computing a minimum S. Our lower bound utilizes a technique in [9]. Finally, we analyze the special case where each individual is convinced of a message when more than half of its in-neighbors are convinced.

Optimal Insertion of a Segment Highway in a City Metric

Matias Korman — 2008-07-04T09:41:35-00:00

Computing and Combinatorics (2008), pp. 611-620.

Given two sets of points in the plane, we are interested in locating a highway h such that an objective function on the city distance between points of the two sets is minimized (where the city distance is measured with speed v > 1 on a highway and 1 in the underlying metric elsewhere). Extending the results of Ahn et al. ([7]), we consider the option that there are already some built highways. We give a unified approach to this problem to design polynomial-time algorithms for several combinations of objective functions and types of the inserted highway (turnpike or freeway).

Transcription factor modularity in a gene-centered C. elegans core neuronal protein-DNA interaction network

Vanessa Vermeirssen — 2008-07-03T19:19:06-00:00

Genome Res., Vol. 17, No. 7. (1 July 2007), pp. 1061-1071.

Transcription regulatory networks play a pivotal role in the development, function, and pathology of metazoan organisms. Such networks are comprised of protein-DNA interactions between transcription factors (TFs) and their target genes. An important question pertains to how the architecture of such networks relates to network functionality. Here, we show that a Caenorhabditis elegans core neuronal protein-DNA interaction network is organized into two TF modules. These modules contain TFs that bind to a relatively small number of target genes and are more systems specific than the TF hubs that connect the modules. Each module relates to different functional aspects of the network. One module contains TFs involved in reproduction and target genes that are expressed in neurons as well as in other tissues. The second module is enriched for paired homeodomain TFs and connects to target genes that are often exclusively neuronal. We find that paired homeodomain TFs are specifically expressed in C. elegans and mouse neurons, indicating that the neuronal function of paired homeodomains is evolutionarily conserved. Taken together, we show that a core neuronal C. elegans protein-DNA interaction network possesses TF modules that relate to different functional aspects of the complete network. 10.1101/gr.6148107

Epidemic dynamics and endemic states in complex networks

Romualdo Pastor-Satorras — 2008-07-03T18:28:23-00:00

Physical Review E, Vol. 63, No. 6. (22 May 2001), 066117.

Epidemic Spreading in Scale-Free Networks

Romualdo Pastor-Satorras — 2007-10-22T19:13:25-00:00

Physical Review Letters, Vol. 86, No. 14. (2 April 2001), 3200.

The Internet has a very complex connectivity recently modeled by the class of scale-free networks. This feature; which appears to be very efficient for a communications network; favors at the same time the spreading of computer viruses. We analyze real data from computer virus infections and find the average lifetime and persistence of viral strains on the Internet. We define a dynamical model for the spreading of infections on scale-free networks; finding the absence of an epidemic threshold and its associated critical behavior. This new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.

The Regularity Lemma and Its Applications in Graph Theory

János Komlós — 2008-07-03T13:25:40-00:00

Theoretical Aspects of Computer Science (2002), pp. 149-152.

Szemerédi’s Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. In the last few years more and more new results were obtained by using the Regularity Lemma, and also some new variants and generalizations appeared. Komlós and Simonovits have written a survey on the topic [96]. The present survey is, in a sense, a continuation of the earlier survey. Here we describe some sample applications and generalizations. To keep the paper self-contained we decided to repeat (sometimes in a shortened form) parts of the first survey, but the emphasis is on new results.

Identification of Functional Information Subgraphs in Complex Networks

Lu\is Bettencourt — 2008-06-30T16:57:31-00:00

Physical Review Letters, Vol. 100, No. 23. (2008)

We present a general information theoretic approach for identifying functional subgraphs in complex networks. We show that the uncertainty in a variable can be written as a sum of information quantities, where each term is generated by successively conditioning mutual informations on new measured variables in a way analogous to a discrete differential calculus. The analogy to a Taylor series suggests efficient optimization algorithms for determining the state of a target variable in terms of functional groups of other nodes. We apply this methodology to electrophysiological recordings of cortical neuronal networks grown in vitro. Each cell's firing is generally explained by the activity of a few neurons. We identify these neuronal subgraphs in terms of their redundant or synergetic character and reconstruct neuronal circuits that account for the state of target cells.