Optimal network alignment with graphlet degree vectors.

Cancer Informatics
Tijana MilenkovićNatasa Przulj

Abstract

Important biological information is encoded in the topology of biological networks. Comparative analyses of biological networks are proving to be valuable, as they can lead to transfer of knowledge between species and give deeper insights into biological function, disease, and evolution. We introduce a new method that uses the Hungarian algorithm to produce optimal global alignment between two networks using any cost function. We design a cost function based solely on network topology and use it in our network alignment. Our method can be applied to any two networks, not just biological ones, since it is based only on network topology. We use our new method to align protein-protein interaction networks of two eukaryotic species and demonstrate that our alignment exposes large and topologically complex regions of network similarity. At the same time, our alignment is biologically valid, since many of the aligned protein pairs perform the same biological function. From the alignment, we predict function of yet unannotated proteins, many of which we validate in the literature. Also, we apply our method to find topological similarities between metabolic networks of different species and build phylogenetic trees based on our network...Continue Reading

References

Oct 1, 1990·Computer Applications in the Biosciences : CABIOS·D GautheretR Cedergren
Oct 5, 1990·Journal of Molecular Biology·S F AltschulD J Lipman
Nov 1, 1994·Protein Science : a Publication of the Protein Society·D V LaurentsM Levitt
Feb 21, 1998·Nucleic Acids Research·J M CherryD Botstein
Jun 12, 1998·Nature·D J Watts, S H Strogatz
Dec 11, 1999·Nucleic Acids Research·M Kanehisa, S Goto
Dec 11, 1999·Nucleic Acids Research·H M BermanP E Bourne
Feb 10, 2000·Molecular Biology and Evolution·P J KeelingJ D Palmer
Jul 10, 2001·Journal of Molecular Evolution·C V Forst, K Schulten
Oct 30, 2001·High Altitude Medicine & Biology·J B West
Dec 26, 2001·Nucleic Acids Research·H W MewesB Weil
Mar 2, 2002·Science·Eric H DavidsonHamid Bolouri
Jul 16, 2002·Molecular & Cellular Proteomics : MCP·Charlotte M DeaneDavid Eisenberg
Jul 12, 2003·Bioinformatics·Maureen Heymans, Ambuj K Singh
Oct 21, 2003·Proceedings of the National Academy of Sciences of the United States of America·Manoj Pratim Samanta, Shoudan Liang
Nov 5, 2003·Bioinformatics·Hasan H Otu, Khalid Sayood
Nov 8, 2003·Science·L GiotJ M Rothberg
Dec 19, 2003·Nucleic Acids Research·Suraj PeriAkhilesh Pandey
Jan 6, 2004·Science·Siming LiMarc Vidal
Jan 31, 2004·Bioinformatics·Minghua DengTing Chen
Feb 13, 2004·Bioinformatics·N PrzuljI Jurisica
Feb 26, 2004·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Minghua DengFengzhu Sun
Mar 20, 2004·Quarterly Reviews of Biophysics·James C Whisstock, Arthur M Lesk
Jun 8, 2004·Bioinformatics·A D KingI Jurisica
Jun 25, 2004·Nucleic Acids Research·Brian P KelleyTrey Ideker
Jul 31, 2004·Bioinformatics·N PrzuljI Jurisica
Sep 28, 2004·Proceedings of the National Academy of Sciences of the United States of America·Johannes Berg, Michael Lässig
Oct 29, 2004·Nature·Ping XuGregory A Buck
Dec 14, 2004·Journal of Biology·Wen ZhangTimothy R Hughes
Jan 22, 2005·Molecular Biology and Evolution·Lesley Collins, David Penny
Jun 21, 2005·Current Opinion in Structural Biology·James D WatsonJanet M Thornton

❮ Previous
Next ❯

Citations

Jun 22, 2012·PloS One·Giovanni CirielloConcettina Guerra
Dec 18, 2013·Bioinformatics·Tomaž Hočevar, Janez Demšar
Jan 21, 2014·Bioinformatics·Noël Malod-Dognin, Nataša Pržulj
May 6, 2014·Bioinformatics·Connor Clark, Jugal Kalita
Aug 26, 2014·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Alex Radu, Michael Charleston
Jul 13, 2014·Bioinformatics·Vikram Saraph, Tijana Milenković
Sep 11, 2012·Bioinformatics·R W SolavaT Milenkovic
Oct 11, 2012·Bioinformatics·Rob Patro, Carl Kingsford
Jan 26, 2013·Bioinformatics·Wayne HayesNataša Pržulj
Feb 16, 2013·Bioinformatics·Ahmet E Aladag, Cesim Erten
Sep 11, 2012·Briefings in Functional Genomics·Vuk Janjić, Nataša Pržulj
Sep 12, 2015·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Fazle Elahi FaisalTijana Milenkovic
Dec 29, 2010·BioEssays : News and Reviews in Molecular, Cellular and Developmental Biology·Nataša Pržulj
May 1, 2014·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Marco Mina, Pietro Hiram Guzzi
Aug 6, 2015·IET Systems Biology·Jiang XieWu Zhang
Feb 11, 2015·Bioinformatics·Connor Clark, Jugal Kalita
Jun 15, 2015·Bioinformatics·Y HulovatyyT Milenković
Jun 15, 2015·Bioinformatics·Sheng WangJian Peng
Sep 3, 2011·PloS One·Tijana MilenkovićNataša Pržulj
Jun 15, 2016·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Jiang XieQing Nie
Aug 8, 2009·PLoS Computational Biology·Oleksii KuchaievNatasa Przulj
Mar 7, 2014·PloS One·Yuriy HulovatyyTijana Milenković
Oct 21, 2014·PloS One·Benjamin Y S LiGenke Yang
Aug 27, 2013·PloS One·Anida SarajlićNataša Pržulj
Sep 4, 2015·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Ahed ElmsallatiJugal Kalita
Oct 11, 2015·BMC Bioinformatics·Md Mahmudul Hasan, Tamer Kahveci
Dec 10, 2016·PloS One·Yiran HuangJing Huang
Jul 15, 2015·Scientific Reports·Brian Law, Gary D Bader
Jun 4, 2015·EURASIP Journal on Bioinformatics & Systems Biology·Fazle E FaisalTijana Milenković
Mar 1, 2015·Bioinformatics·Noël Malod-Dognin, Nataša Pržulj
Dec 14, 2016·BMC Bioinformatics·Ehsan KazemiHassan Pezeshgi Modarres
May 23, 2013·Bioinformatics·Behnam NeyshaburSeyed Shahriar Arab
Jan 24, 2017·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Ahed ElmsallatiJugal Kalita
Oct 25, 2016·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Jiaxiang HuangLijia Ma
Aug 3, 2016·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Shahin MohammadiAnanth Grama
Aug 23, 2017·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Vipin Vijayan, Tijana Milenkovic
Jan 12, 2012·Integrative Biology : Quantitative Biosciences From Nano to Macro·Vesna Memišević, Nataša Pržulj
Feb 14, 2019·Bioinformatics·David AparícioFernando Silva
May 11, 2011·Expert Review of Anticancer Therapy·Sarah J L PayneSarah Slater
Feb 23, 2020·Frontiers in Bioengineering and Biotechnology·Mikaela KoutrouliGeorgios A Pavlopoulos

❮ Previous
Next ❯

Methods Mentioned

BETA
two-hybrid

Software Mentioned

CiteXplorer
GRAph ALigner ( GRAAL )
GRAAL GRAph ALigner
BLAST
GRAAL
IsoRank

Related Concepts

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Blastomycosis

Blastomycosis fungal infections spread through inhaling Blastomyces dermatitidis spores. Discover the latest research on blastomycosis fungal infections here.

Nuclear Pore Complex in ALS/FTD

Alterations in nucleocytoplasmic transport, controlled by the nuclear pore complex, may be involved in the pathomechanism underlying multiple neurodegenerative diseases including Amyotrophic Lateral Sclerosis and Frontotemporal Dementia. Here is the latest research on the nuclear pore complex in ALS and FTD.

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Position Effect Variegation

Position Effect Variagation occurs when a gene is inactivated due to its positioning near heterochromatic regions within a chromosome. Discover the latest research on Position Effect Variagation here.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Microbicide

Microbicides are products that can be applied to vaginal or rectal mucosal surfaces with the goal of preventing, or at least significantly reducing, the transmission of sexually transmitted infections. Here is the latest research on microbicides.

Related Papers

Journal of the Royal Society, Interface
Oleksii KuchaievNatasa Przulj
Integrative Biology : Quantitative Biosciences From Nano to Macro
Vesna Memišević, Natasa Przulj
Proceedings of the National Academy of Sciences of the United States of America
Brian P KelleyTrey Ideker
Nucleic Acids Research
Kevin P O'BrienErik L L Sonnhammer
© 2021 Meta ULC. All rights reserved