Computer Science Research Works
Permanent URI for this collectionhttp://hdl.handle.net/1903/1593
Browse
2 results
Search Results
Item Global Network Alignment Using Multiscale Spectral Signatures(2011) Patro, Rob; Kingsford, CarlMotivation: Protein interaction networks provide an important system-level view of biological processes. One of the fundamental problems in biological network analysis is the global alignment of a pair of networks, which puts the proteins of one network into correspondence with the proteins of another network in a manner that conserves their interactions while respecting other evidence of their homology. By providing a mapping between the networks of different species, alignments can be used to inform hypotheses about the functions of unannotated proteins, the existence of unobserved interactions, the evolutionary divergence between the two species and the evolution of complexes and pathways. Results: We introduce GHOST, a global pairwise network aligner that uses a novel spectral signature to measure topological similarity across disparate networks. It exhibits state-of-the-art performance on several network alignment tasks. We show that the spectral signature used by GHOST is highly discriminative, while the alignments it produces are also robust to experimental noise. When compared with other recent approaches, we find that GHOST is able to recover larger and biologically-significant, shared subnetworks between species. Availability: An efficient and parallelized implementation of GHOST, released under the Apache 2.0 license, is available at http:// cbcb.umd.edu/kingsford-group/ghostItem Graph rigidity reveals non-deformable collections of chromosome conformation constraints(2011-12-14) Duggal, Geet; Kingsford, CarlMotivation: The physical structure of chromatin is associated with a variety of biological phenomena including long-range regulation, chromosome rearrangements, and somatic copy number alterations. Chromosome conformation capture is a recent experimental technique that results in pairwise proximity measurements between chromosome locations in a genome. This information can be used to construct three-dimensional models of portions of chromosomes or entire genomes using a variety of recently proposed algorithms. However, it is possible that these distance measurements do not provide the proper constraints to uniquely specify such an embedding. It is therefore necessary to separate regions of the chromatin structure that are sufficiently constrained from regions with measurements that suggest a more pliable structure. This separation will allow studies of correlations betweeen chromatin organization and genome function to be targeted to the sufficiently constrained, high-confidence substructures within an embedding. Results: Using rigidity theory, we introduce a novel, fast algorithm for identifying high-confidence (rigid) substructures within graphs that result from chromosome conformation capture experiments. We apply the method to four recent chromosome conformation capture data sets and find that for even stringently filtered experimental constraints, a large rigid region spans most of the genome. We find that the organization of rigid components depends crucially on short-range interactions within the genome. We also find that rigid component boundaries appear at regions associated with areas of low nucleosome density and that properties of rigid, subtelomeric regions are consistent with light microscopy data. Availability: The software for identifying rigid components is GPL-Licensed and available for download at http://www.cbcb.umd.edu/kingsford-group/starfish. Contact: carlk@cs.umd.edu