MOTIVATION: Large-scale sequencing projects have confirmed the hypothesis that eukaryotic DNA is rich in repetitions whose functional role needs to be elucidated. In particular, tandem repeats (TRs) (i.e. short, almost identical sequences that lie adjacent to each other) have been associated to many cellular processes and, indeed, are also involved in several genetic disorders. The need of comprehensive lists of TRs for association studies and the absence of a computational model able to capture their variability have revived research on discovery algorithms. RESULTS: Building upon the idea that sequence similarities can be easily displayed using graphical methods, we formalized the structure that TRs induce in dot-plot matrices where a sequence is compared with itself. Leveraging on the observation that a compact representation of these matrices can be built and searched in linear time, we developed Dot2dot: an accurate algorithm fast enough to be suitable for whole-genome discovery of TRs. Experiments on five manually curated collections of TRs have shown that Dot2dot is more accurate than other established methods, and completes the analysis of the biggest known reference genome in about one day on a standard PC. AVAILABILITY AND IMPLEMENTATION: Source code and datasets are freely available upon paper acceptance at the URL: https://github.com/Gege7177/Dot2dot. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Biological networks play an increasingly important role in the exploration of functional modularity and cellular organization at a systemic level. Quite often the first tools used to analyze these networks are clustering algorithms. We concentrate here on the specific task of predicting protein complexes (PC) in large protein-protein interaction networks (PPIN). Currently, many state-of-the-art algorithms work well for networks of small or moderate size. However, their performance on much larger networks, which are becoming increasingly common in modern proteome-wise studies, needs to be re-assessed. RESULTS AND DISCUSSION: We present a new fast algorithm for clustering large sparse networks: Core&Peel, which runs essentially in time and storage O(a(G)m+n) for a network G of n nodes and m arcs, where a(G) is the arboricity of G (which is roughly proportional to the maximum average degree of any induced subgraph in G). We evaluated Core&Peel on five PPI networks of large size and one of medium size from both yeast and homo sapiens, comparing its performance against those of ten state-of-the-art methods. We demonstrate that Core&Peel consistently outperforms the ten competitors in its ability to identify known protein complexes and in the functional coherence of its predictions. Our method is remarkably robust, being quite insensible to the injection of random interactions. Core&Peel is also empirically efficient attaining the second best running time over large networks among the tested algorithms. CONCLUSIONS: Our algorithm Core&Peel pushes forward the state-of the-art in PPIN clustering providing an algorithmic solution with polynomial running time that attains experimentally demonstrable good output quality and speed on challenging large real networks.

Controlling the differential expression of many thousands different genes at any given time is a fundamental task of metazoan organisms and this complex orchestration is controlled by the so-called regulatory genome encoding complex regulatory networks: several Transcription Factors bind to precise DNA regions, so to perform in a cooperative manner a specific regulation task for nearby genes. The in silico prediction of these binding sites is still an open problem, notwithstanding continuous progress and activity in the last two decades. In this paper, we describe a new efficient combinatorial approach to the problem of detecting sets of cooperating binding sites in promoter sequences, given in input a database of Transcription Factor Binding Sites encoded as Position Weight Matrices. We present CMStalker, a software tool for composite motif discovery which embodies a new approach that combines a constraint satisfaction formulation with a parameter relaxation technique to explore efficiently the space of possible solutions. Extensive experiments with 12 data sets and 11 state-of-the-art tools are reported, showing an average value of the correlation coefficient of 0.54 (against a value 0.41 of the closest competitor). This improvements in output quality due to CMStalker is statistically significant.

Social networks have demonstrated in the last few years to be a powerful and flexible concept useful to represent and analyze data emerging form social interactions and social activities. The study of these networks can thus provide a deeper understanding of many emergent global phenomena. The amount of data available in the form of social networks data is growing by the day, and this poses many computational challenging problems for their analysis. In fact many analysis tools suitable to analyze small to medium sized networks are inefficient for large social networks. The computation of the betweenness centrality index is a well established method for network data analysis and it is also important as subroutine in more advanced algorithms, such as the Girvan-Newman method for graph partitioning. In this paper we present a new approach for the computation of the betweenness centrality, which speeds up considerably Brandes' algorithm (the current state of the art) in the context of social networks. Our approach exploits the natural sparsity of the data to algebraically (and efficiently) determine the betweenness of those nodes forming trees (tree-nodes) in the social network. Moreover, for the residual network, which is often of much smaller size, we modify directly the Brandes' algorithm so that we can remove the nodes already processed and perform the computation of the shortest paths only for the residual nodes. Tests conducted on a sample of publicly available large networks from the Stanford repository show that improvements of a factor ranging between 2 and 5 are possible on several such graphs, when the sparsity, measured by the ratio of tree-nodes to the total number of nodes, is in a medium range (30% to 50%). For some large networks from the Stanford repository and for a sample of social networks provided by Sistemi Territoriali with high sparsity (80% and above) tests show that our algorithm consistently runs between one and two orders of magnitude faster than the current state of the art exact algorithm.

BACKGROUND: Tandem repetitions within protein amino acid sequences often correspond to regular secondary structures and form multi-repeat 3D assemblies of varied size and function. Developing internal repetitions is one of the evolutionary mechanisms that proteins employ to adapt their structure and function under evolutionary pressure. While there is keen interest in understanding such phenomena, detection of repeating structures based only on sequence analysis is considered an arduous task, since structure and function is often preserved even under considerable sequence divergence (fuzzy tandem repeats). RESULTS: In this paper we present PTRStalker, a new algorithm for ab-initio detection of fuzzy tandem repeats in protein amino acid sequences. In the reported results we show that by feeding PTRStalker with amino acid sequences from the UniProtKB/Swiss-Prot database we detect novel tandemly repeated structures not captured by other state-of-the-art tools. Experiments with membrane proteins indicate that PTRStalker can detect global symmetries in the primary structure which are then reflected in the tertiary structure. CONCLUSIONS: PTRStalker is able to detect fuzzy tandem repeating structures in protein sequences, with performance beyond the current state-of-the art. Such a tool may be a valuable support to investigating protein structural properties when tertiary X-ray data is not available.

BACKGROUND: Tandem repeats are multiple duplications of substrings in the DNA that occur contiguously, or at a short distance, and may involve some mutations (such as substitutions, insertions, and deletions). Tandem repeats have been extensively studied also for their association with the class of repeat expansion diseases (mostly affecting the nervous system). Comparative studies on the output of different tools for finding tandem repeats highlighted significant differences among the sets of detected tandem repeats, while many authors pointed up how critical it is the right choice of parameters. RESULTS: In this paper we present TReaDS - Tandem Repeats Discovery Service, a tandem repeat meta search engine. TReaDS forwards user requests to several state of the art tools for finding tandem repeats and merges their outcome into a single report, providing a global, synthetic, and comparative view of the results. In particular, TReaDS allows the user to (i) simultaneously run different algorithms on the same data set, (ii) choose for each algorithm a different setting of parameters, and (iii) obtain a report that can be downloaded for further, off-line, investigations. We used TReaDS to investigate sequences associated with repeat expansion diseases. CONCLUSIONS: By using the tool TReaDS we discover that, for 27 repeat expansion diseases out of a currently known set of 29, long fuzzy tandem repeats are covering the expansion loci. Tests with control sets confirm the specificity of this association. This finding suggests that long fuzzy tandem repeats can be a new class of cis-acting elements involved in the mechanisms leading to the expansion instability.We strongly believe that biologists can be interested in a tool that, not only gives them the possibility of using multiple search algorithm at the same time, with the same effort exerted in using just one of the systems, but also simplifies the burden of comparing and merging the results, thus expanding our capabilities in detecting important phenomena related to tandem repeats.

MOTIVATION: Genomes in higher eukaryotic organisms contain a substantial amount of repeated sequences. Tandem Repeats (TRs) constitute a large class of repetitive sequences that are originated via phenomena such as replication slippage and are characterized by close spatial contiguity. They play an important role in several molecular regulatory mechanisms, and also in several diseases (e.g. in the group of trinucleotide repeat disorders). While for TRs with a low or medium level of divergence the current methods are rather effective, the problem of detecting TRs with higher divergence (fuzzy TRs) is still open. The detection of fuzzy TRs is propaedeutic to enriching our view of their role in regulatory mechanisms and diseases. Fuzzy TRs are also important as tools to shed light on the evolutionary history of the genome, where higher divergence correlates with more remote duplication events. RESULTS: We have developed an algorithm (christened TRStalker) with the aim of detecting efficiently TRs that are hard to detect because of their inherent fuzziness, due to high levels of base substitutions, insertions and deletions. To attain this goal, we developed heuristics to solve a Steiner version of the problem for which the fuzziness is measured with respect to a motif string not necessarily present in the input string. This problem is akin to the 'generalized median string' that is known to be an NP-hard problem. Experiments with both synthetic and biological sequences demonstrate that our method performs better than current state of the art for fuzzy TRs and that the fuzzy TRs of the type we detect are indeed present in important biological sequences. AVAILABILITY: TRStalker will be integrated in the web-based TRs Discovery Service (TReaDS) at bioalgo.iit.cnr.it. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The detection of an over-represented sub-sequence in a set of (carefully chosen) DNA sequences is often the main clue leading to the investigation of a possible functional role for such a subsequence. Over-represented substrings (with possibly local mutations) in a biological string are termed motifs. A typical functional unit that can be modeled by a motif is a Transcription Factor Binding Site (TFBS), a portion of the DNA sequence apt to the binding of a protein that participates in complex transcriptomic biochemical reactions. In the literature it has been proposed a simplified combinatorial problem called the planted (l-d)-motif problem (known also as the (l-d) Challenge Problem) that captures the essential combinatorial nature of the motif finding problem. In this paper we propose a novel graph-based algorithm for solving a refinement of the (l-d) Challenge Problem. Experimental results show that instances of the (l-d) Challenge Problem considered difficult for competing state of the art methods in literature can be solved efficiently in our framework.

The World Wide Web (WWW) is rapidly becoming important for society as a medium for sharing data, information, and services, and there is a growing interest in tools for understanding collective behavior and emerging phenomena in the WWW. In this article we focus on the problem of searching and classifying communities in the Web. Loosely speaking a community is a group of pages related to a common interest. More formally, communities have been associated in the computer science literature with the existence of a locally dense subgraph of the Web graph (where Web pages are nodes and hyperlinks are arcs of the Web graph). The core of our contribution is a new scalable algorithm for finding relatively dense subgraphs in massive graphs. We apply our algorithm on Web graphs built on three publicly available large crawls of the Web (with raw sizes up to 120M nodes and 1G arcs). The effectiveness of our algorithm in finding dense subgraphs is demonstrated experimentally by embedding artificial communities in the Web graph and counting how many of these are blindly found. Effectiveness increases with the size and density of the communities: it is close to 100% for communities of thirty nodes or more (even at low density). It is still about 80% even for communities of twenty nodes with density over 50% of the arcs present. At the lower extremes the algorithm catches 35% of dense communities made of ten nodes. We also develop some sufficient conditions for the detection of a community under some local graph models and not-too-restrictive hypotheses. We complete our Community Watch system by clustering the communities found in the Web graph into homogeneous groups by topic and labeling each group by representative keywords.

A tool to provide an idea of the content of a given video is becoming a need in the current Web scenario, where the presence of videos is increasing day after day. Dynamic summarization techniques can be used to this aim as they set up a video abstract, by selecting and sequencing short video clips extracted from the original video. Needless to say, the selection process is critical. In this paper we focus our attention on clustering algorithms to provide such selection and we investigate the effects of their employment in the Web scenario. Clustering algorithms are very effective in producing static video summary, but few works consider them for video abstract production. For this reason, we set up an experimental scenario where we investigate their performance considering different categories of video, different abstract lengths and different low-level video analysis. Results show that clustering techniques can be useful only for some categories of videos and only if the selection process is based on video scene characteristics. Furthermore, the investigation also shows that to provide a customized service (user can freely decide the abstract time length), only fast clustering algorithm should be used.

Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNP's present in a chromosome (called the haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper we propose a new heuristic method for the problem of haplotype reconstruction for (portions of) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. When gaps are considered no exact method of polynomial complexity is known. The problem is also hard to approximate with guarantees. Therefore fast heuristics have been proposed. In this paper we describe SpeedHap, a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20%) and low coverage (as low as 3). We test SpeedHap on real data from the HapMap Project.

The World Wide Web (WWW) is rapidly becoming important for society as a medium for sharing data, information and services, and there is a growing interest in tools for understanding collective behaviors and emerging phenomena in the WWW. In this paper we focus on the problem of searching and classifying communities in the web. Loosely speaking a community is a group of pages related to a common interest. More formally communities have been associated in the computer science literature with the existence of a locally dense sub-graph of the web-graph (where web pages are nodes and hyper-links are arcs of the web-graph). The core of our contribution is a new scalable algorithm for finding relatively dense subgraphs in massive graphs. We apply our algorithm on web-graphs built on three publicly available large crawls of the web (with raw sizes up to 120M nodes and 1G arcs). The effectiveness of our algorithm in finding dense subgraphs is demonstrated experimentally by embedding artificial communities in the web-graph and counting how many of these are blindly found. Effectiveness increases with the size and density of the communities: it is close to 100% for communities of a thirty nodes or more (even at low density). It is still about 80% even for communities of twenty nodes with density over 50% of the arcs present. At the lower extremes the algorithm catches 35% of dense communities made of ten nodes. We complete our Community Watch system by clustering the communities found in the web-graph into homogeneous groups by topic and labelling each group by representative keywords.

Packet classification is a common task in modern Internet routers. The goal is to classify packets into "classes" or "flows" according to some ruleset that looks at multiple fields of each packet. Differentiated actions can then be applied to the traffic depending on the result of the classification. Even though rulesets can be expressed in a relatively compact way by using high level languages, the resulting decision trees can partition the search space (the set of possible attribute values) in a potentially very large (106 and more) number of regions. This calls for methods that scale to such large problem sizes, though the only scalable proposal in the literature so far is the one based on a fat inverted segment tree (A. Feldmann and S. Muthukrishnan). In this paper we propose a new geometric technique called G-filter for packet classification on d dimensions. G-filter is based on an improved space decomposition technique. In addition to a theoretical analysis showing that classification in G-filter has O(1) time complexity and slightly super-linear space in the number of rules, we provide thorough experiments showing that the constants involved are extremely small on a wide range of problem sizes, and that G-filter improve the best results in the literature for large problem sizes, and is competitive for small sizes as well.

IP address lookup is a critical operation for high bandwidth routers in packet switching networks such as Internet. The lookup is a non-trivial operation since it requires searching for the longest prefix, among those stored in a (large) given table, matching the IP address. Ever increasing routing tables size, traffic volume and links speed demand new and more efficient algorithms. Moreover, the imminent move to IPv6 128-bit addresses will soon require a rethinking of previous technical choices. This article describes a the new data structure for solving the IP table look up problem christened the Adaptive Stratified Tree (AST). The proposed solution is based on casting the problem in geometric terms and on repeated application of efficient local geometric optimization routines. Experiments with this approach have shown that in terms of storage, query time and update time the AST is at a par with state of the art algorithms based on data compression or string manipulations (and often it is better on some of the measured quantities). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Article A geometric approach to computing higher order form factors Share on Author: Marco Pellegrini Istituto di Matematica Computazionale del CNR, Via S.Maria 46, 56126-Pisa (Italy) Istituto di Matematica Computazionale del CNR, Via S.Maria 46, 56126-Pisa (Italy)View Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 69–78https://doi.org/10.1145/304893.304914Online:13 June 1999Publication History 0citation294DownloadsMetricsTotal Citations0Total Downloads294Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The following problems that arise in the computation of electrostatic forces and in the Boundary Element Method are considered. Given two convex interior-disjoint polyhedra in 3-space endowed with a volume charge density which is a polynomial in the Cartesian coordinates of R 3 , compute the Coulomb force acting on them. Given two interior-disjoint polygons in 3-space endowed with a surface charge density which is polynomial in the Cartesian coordinates of R 3 , compute the normal component of the Coulomb force acting on them. For both problems adaptive Gaussian approximation algorithms are given, which, for n Gaussian points, in time O( n ), achieve absolute error O(c -√n ) for a constant c > 1. Such a result improves upon previously known best asymptotic bounds. This result is achieved by blending techniques from integral geometry, computational geometry and numerical analysis. In particular, integral geometry is used in order to represent the forces as integrals whose kernal is free from singularities.

Let U be a set of n possibly intersecting $(d - 1)$-simplices in d-space for $d \geqslant 2$, and let $\mathcal{A}(U)$ be the arrangement of U. Let $K = |\mathcal{A}(U)|$ be the number of faces of any dimension in the arrangement of U. A data structure is described that uses storage $O(n^{d - 1 + \epsilon } + K)$ and is built deterministically in time $O(n^{d - 1 + \epsilon } + K\log n)$ where $\epsilon > 0$ is an arbitrarily small constant, such that the face of $\mathcal{A}(U)$ containing a query point is located in time $O(\log ^3 n)$. If two query points are in the same cell of $\mathcal{A}(U)$, a collision-free path connecting them is produced. This result is obtained by exploiting powerful and so far overlooked properties of sparse nets introduced by Chazelle [Discrete Comput. Geom., 9 (1993), pp. 145–158]. If the $(d - 1)$-simplices in U have pairwise-disjoint interiors and $d \geqslant 3$, improved bounds are obtained. A data structure is described that uses $O(n^{d - 1} )$ storage and is built deterministically in time $O(n^{d - 1} )$ such that point-location queries are solved in time $O(\log n)$. Also, as a by-product, this method gives the first optimal worst-case algorithm for triangulating a nonsimple polyhedron in 3-space.

The exchange of radiant energy (e.g.visible light, the random choices of the algorithm and the result holds for any iuput.

d-1)-simplices in d-space, for d ~2; and let A(S)

The problem of detecting efficiently whether a query simplex is collision free among polyhedral obstacles is considered. If n is the number of vertices, edges, and faces of the polyhedral obstacles, and m is the amount of storage allocated for the data structure $(n^{1 + \epsilon } \leqslant m \leqslant n^{4 + \epsilon } )$, it is possible to solve collision-free placements queries for simplices in time $O({{n^{1 + \epsilon } } / {m^{{1 / 4}} }})$ for any $ \epsilon > 0$, where the constants depend on $ \epsilon $. In order to solve this problem the authors develop data structures to detect on-line intersections of query half planes with sets of lines and segments. Some nearest-neighbor problems for objects in 3-space are also considered. Given a set of n lines in 3-space, the shortest vertical segment between any pair of lines is found in randomized expected time $O(n^{{8 / 5} + \epsilon } )$ for every $ \epsilon > 0$. The longest connecting vertical segment is found in time $O(n^{{4 / 3} + \in } )$ The shortest connecting segment is found in time $O(n^{{5 / 3} + \epsilon } )$.

We study some combinatorial and algorithmic problems on sets of lines and polyhedral objects in 3-space. Our main results include:

In this paper efficient algorithms for counting intersections in a collection of circles or circular arcs are presented. An algorithm for counting intersections in a collection of n circles is presented whose running time is $O(n^{{3 / {2 + \epsilon }}} )$, for any $\epsilon > 0$ is presented. Using this algorithm as a subroutine, it is shown that the intersections in a set of n circular arcs can also be counted in time $O(n^{{3 / {2 + \epsilon }}} )$. If all arcs have the same radius, the running time can be improved to $O(n^{{4 / {3 + \epsilon }}} )$, for any $\epsilon > 0$.

In the first part of the paper we solve the problem of detecting efficiently if a query simplex is collison-free among polyhedral obstacles. In order to solve this problem we develop new on-line data structures to detect intersections of query halfplanes with sets of lines and segments.

In this paper we consider the following problems: given a set T of triangles in 3-space, with |T| = n,