short-paper

Public Access

A Network Science Approach for Determining the Ancestral Phylum of Bacteria

Authors:

Ehdieh Khaledian,

Assefaw H. Gebremedhin,

Kelly A. Brayton,

Shira L. BroschatAuthors Info & Claims

BCB '18: Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics

Pages 398 - 403

https://doi.org/10.1145/3233547.3233575

Published: 15 August 2018 Publication History

Abstract

Perhaps the most important organizing principle in biology for bac- teria is the tree of phyla. It represents the evolution of bacteria now living in virtually every environment. The availability of whole genome sequences has provided the opportunity to reconstruct a comprehensive view of the tree and to trace the shared ancestry among all bacteria that have been sequenced. However, most exist- ing research has presented the tree of phyla without considering the ancestral phylum. The objective of this study is to fi nd the ancestral phylum using a network science approach and exploiting the availability of a rich dataset of genomes. For the analysis, a network representing 210 organisms is created by clustering more than 700,000 protein sequences for 28 recognized phyla. A network of phyla is then extracted from the results which is examined using a breadth-fi rst search algorithm and centrality measures to create a rooted tree from which the likely ancestral phylum is identified.

References

[1]

Michael Baur, Marc Benkert, Ulrik Brandes, Sabine Cornelsen, Marco Gaertler, Boris Köpf, Jürgen Lerner, and Dorothea Wagner. 2001. Visone Software for visual social network analysis. In International Symposium on Graph Drawing. Springer, 463--464.

[2]

Ludmila Chistoserdova. 2016. Wide distribution of genes for tetrahydromethanopterin/methanofuran-linked C1 transfer reactions argues for their presence in the common ancestor of bacteria and archaea. Frontiers in microbiology 7 (2016), 1425.

[3]

Seung-Seok Choi, Sung-Hyuk Cha, and Charles C Tappert. 2010. A survey of binary similarity and distance measures. Journal of Systemics, Cybernetics and Informatics 8, 1 (2010), 43--48.

[4]

Francesca D Ciccarelli, Tobias Doerks, Christian Von Mering, Christopher J Creevey, Berend Snel, and Peer Bork. 2006. Toward automatic reconstruction of a highly resolved tree of life. science 311, 5765 (2006), 1283--1287.

[5]

Jeff Daily. 2016. Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments. BMC bioinformatics 17, 1 (2016), 81.

[6]

Frédéric Delsuc, Henner Brinkmann, and Hervé Philippe. 2005. Phylogenomics and the reconstruction of the tree of life. Nature Reviews Genetics 6, 5 (2005), 361.

[7]

AE Douglas. 1998. Nutritional interactions in insect-microbial symbioses: aphids and their symbiotic bacteria Buchnera. Annual review of entomology 43, 1 (1998), 17--37.

[8]

Claire M Fraser, Jeannine D Gocayne, Owen White, Mark D Adams, Rebecca A Clayton, Robert D Fleischmann, Carol J Bult, Anthony R Kerlavage, Granger Sutton, Jenny M Kelley, et al. 1995. The minimal gene complement of Mycoplasma genitalium. Science 270, 5235 (1995), 397--404.

[9]

Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner. 2016. Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining 6, 1 (2016), 22.

[10]

Laura A Hug, Brett J Baker, Karthik Anantharaman, Christopher T Brown, Alexander J Probst, Cindy J Castelle, Cristina N Butterfield, Alex W Hernsdorf, Yuki Amano, Kotaro Ise, et al. 2016. A new view of the tree of life. Nature microbiology 1 (2016), 16048.

[11]

Erich D Jarvis, Siavash Mirarab, Andre J Aberer, Bo Li, Peter Houde, Cai Li, Simon YW Ho, Brant C Faircloth, Benoit Nabholz, Jason T Howard, et al. 2014. Whole-genome analyses resolve early branches in the tree of life of modern birds. Science 346, 6215 (2014), 1320--1331.

[12]

Charles E Leiserson and Tao B Schardl. 2010. A work-efficient parallel breadthfirst search algorithm (or how to cope with the nondeterminism of reducers). In Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures. ACM, 303--314.

Digital Library

[13]

Gerd Lindner, Christian L Staudt, Michael Hamann, Henning Meyerhenke, and Dorothea Wagner. 2015. Structure-preserving sparsification of social networks. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015. ACM, 448--454.

Digital Library

[14]

Svetlana Lockwood, Kelly A Brayton, and Shira L Broschat. 2016. Comparative genomics reveals multiple pathways to mutualism for tick-borne pathogens. BMC genomics 17, 1 (2016), 481.

[15]

Hao Lu, Mahantesh Halappanavar, and Ananth Kalyanaraman. 2015. Parallel heuristics for scalable community detection. Parallel Comput. 47 (2015), 19--37.

Digital Library

[16]

Aidan C Parte. 2013. LPSN list of prokaryotic names with standing in nomenclature. Nucleic acids research 42, D1 (2013), D613--D616.

[17]

Frederik Schulz, Emiley A Eloe-Fadrosh, Robert M Bowers, Jessica Jarett, Torben Nielsen, Natalia N Ivanova, Nikos C Kyrpides, and Tanja Woyke. 2017. Towards a balanced view of the bacterial tree of life. Microbiome 5, 1 (2017), 140.

[18]

Shuji Shigenobu, Hidemi Watanabe, Masahira Hattori, Yoshiyuki Sakaki, and Hajime Ishikawa. 2000. Genome sequence of the endocellular bacterial symbiont of aphids Buchnera sp. APS. Nature 407, 6800 (2000), 81.

[19]

Madeline C Weiss, Filipa L Sousa, Natalia Mrnjavac, Sinje Neukirchen, Mayo Roettger, Shijulal Nelson-Sathi, and William F Martin. 2016. The physiology and habitat of the last universal common ancestor. Nature Microbiology 1, 9 (2016), 16116.

[20]

Carl R Woese and George E Fox. 1977. Phylogenetic structure of the prokaryotic domain: the primary kingdoms. Proceedings of the National Academy of Sciences 74, 11 (1977), 5088--5090.

[21]

Ting-Ting Xu, Jing Chen, Li-Yun Jiang, and Ge-Xia Qiao. 2017. Historical and cospeciating associations between Cerataphidini aphids (Hemiptera: Aphididae: Hormaphidinae) and their primary endosymbiont Buchnera aphidicola. Zoological Journal of the Linnean Society (2017).

Cited By

Khaledian EBrayton KBroschat S(2020)A Systematic Approach to Bacterial Phylogeny Using Order Level Sampling and Identification of HGT Using Network ScienceMicroorganisms10.3390/microorganisms80203128:2(312)Online publication date: 24-Feb-2020
https://doi.org/10.3390/microorganisms8020312
Khaledian EBroschat S(2020) A study of pClust settings ACM SIGBioinformatics Record10.1145/3411750.341175111:1(1-5)Online publication date: 22-Jul-2020
https://doi.org/10.1145/3411750.3411751

Index Terms

A Network Science Approach for Determining the Ancestral Phylum of Bacteria
1. Applied computing
  1. Life and medical sciences
    1. Bioinformatics
    2. Computational biology
      1. Biological networks
      2. Molecular structural biology
2. Hardware
  1. Emerging technologies
    1. Biology-related information processing

Recommendations

Ancestral genome reconstruction in bacteria
Reconstructing contiguous regions of an ancestral genome
Reconstructing the architecture of the ancestral amniote genome

Motivation: The ancestor of birds and mammals lived approximately 300 million years ago. Inferring its genome organization is key to understanding the differentiated evolution of these two lineages. However, detecting traces of its chromosomal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

BCB '18: Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics

August 2018

727 pages

ISBN:9781450357944

DOI:10.1145/3233547

General Chairs:
Amarda Shehu
George Mason University, USA
,
Cathy Wu
University of Delaware, USA
,
Program Chairs:
Christina Boucher
University of Florida, USA
,
Jing Li
Case Western Reserve University, USA
,
Hongfang Liu
Mayo Clinic, USA
,
Mihai Pop
University of Maryland, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBio: ACM Special Interest Group on Bioinformatics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 August 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

National Science Foundation

Conference

BCB '18

Sponsor:

SIGBio

BCB '18: 9th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics

August 29 - September 1, 2018

DC, Washington, USA

Acceptance Rates

BCB '18 Paper Acceptance Rate 46 of 148 submissions, 31%;

Overall Acceptance Rate 254 of 885 submissions, 29%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
232
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)7

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khaledian EBrayton KBroschat S(2020)A Systematic Approach to Bacterial Phylogeny Using Order Level Sampling and Identification of HGT Using Network ScienceMicroorganisms10.3390/microorganisms80203128:2(312)Online publication date: 24-Feb-2020
https://doi.org/10.3390/microorganisms8020312
Khaledian EBroschat S(2020) A study of pClust settings ACM SIGBioinformatics Record10.1145/3411750.341175111:1(1-5)Online publication date: 22-Jul-2020
https://doi.org/10.1145/3411750.3411751

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents