Proceeding talk – Theme: Systems.
Abstract
The dramatic decrease in the cost of sequencing has resulted in the generation of huge amounts of genomic data. Due to the large redundancies among genomic sequences of individuals from the same species, most of the medical research deals with the variants in the sequences as compared with a reference sequence. Consequently, millions of genomes represented as variants are stored in databases. These databases are constantly updated and queried to extract information such as the common variants among individuals or groups of individuals. Previous algorithms for compression of this type of databases lack efficient random access capabilities, rendering querying the database for particular variants and/or individuals extremely inefficient. We present a new algorithm GTRAC, that achieves significant compression ratios while allowing fast random access over the compressed database. GTRAC uses and adapts techniques from information theory, such as a specialized Lempel-Ziv compressor, and tailored succinct data structures.Motivation. As an increasing amount of protein-protein interaction data becomes available, their computational interpretation has become an important problem in bioinformatics. Specifically, the alignment of the corresponding PPI networks provides valuable information about conserved subnetworks, evolutionary pathways, and functional orthologs. Although several methods have been proposed for global network alignment, there is still a need for methods that produce more accurate alignments in terms of both topological and functional consistency. Results: In this work, we present a novel global network alignment algorithm, ModuleAlign, which makes use of local topology information to define a module-based homology score. It uses a hierarchical clustering strategy to find the functionally coherent proteins involved in the same module. ModuleAlign also employs a novel iterative strategy to find the alignment between a pair of networks. Tested on a diverse set of benchmarks, our experimental results indicate that ModuleAlign outperforms state-of-the-art methods in producing functionally consistent alignments.
Authors
Somaye Hashemifar, Toyota Technological Institute at Chicago, United States
Jianzhu Ma, Toyota Technological Institute at Chicago, United States
Hammad Naveed, Toyota Technological Institute at Chicago, United States
Stefan Canzar, Toyota Technological Institute at Chicago, United States
Jinbo Xu, Toyota Technological Institute at Chicago, United States
Cheng Wang, Toyota Technological Institute at Chicago, United States