Scaffolding of Ancient Contigs and Ancestral Reconstruction in a Phylogenetic Framework
Pages 2094 - 2100
Abstract
Ancestral genome reconstruction is an important task to analyze the evolution of genomes. Recent progress in sequencing ancient DNA led to the publication of so-called paleogenomes and allows the integration of this sequencing data in genome evolution analysis. However, the de novo assembly of ancient genomes is usually fragmented due to DNA degradation over time among others. Integrated phylogenetic assembly addresses the issue of genome fragmentation in the ancient DNA assembly while aiming to improve the reconstruction of all ancient genomes in the phylogeny simultaneously. The fragmented assembly of the ancient genome can be represented as an assembly graph, indicating contradicting ordering information of contigs. In this setting, our approach is to compare the ancient data with extant finished genomes. We generalize a reconstruction approach minimizing the Single-Cut-or-Join rearrangement distance towards multifurcating trees and include edge lengths to improve the reconstruction in practice. This results in a polynomial time algorithm that includes additional ancient DNA data at one node in the tree, resulting in consistent reconstructions of ancestral genomes.
References
[1]
D. Bertrand, Y. Gagnon, M. Blanchette, and N. El-Mabrouk, "Reconstruction of ancestral genome subject to whole genome duplication, speciation, rearrangement and loss," in Proc. Int. Workshop Algorithms Bioinf., 2010, pp. 78-89.
[2]
G. Bourque and P. A. Pevzner, "Genome-scale evolution: Reconstructing gene orders in the ancestral species," Genome Res., vol. 12, no. 1, pp. 26-36, 2002.
[3]
C. Chauve and E. Tannier, "A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes," PLoS Comput. Biol., vol. 4, no. 11, 2008, Art. no. e1000234.
[4]
J. Ma, L. Zhang, B. B. Suh, B. J. Raney, R. C. Burhans, W. J. Kent, M. Blanchette, D. Haussler, and W. Miller, "Reconstructing contiguous regions of an ancestral genome," Genome Res., vol. 16, no. 12, pp. 1557-1565, 2006.
[5]
J. Stoye and R. Wittler, "A unified approach for reconstructing ancient gene clusters," IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 6, no. 3, pp. 387-400, Jul.-Sep. 2009.
[6]
C. Zheng and D. Sankoff, "On the PATHGROUPS approach to rapid small phylogeny," BMC Bioinf., vol. 12, 2011, Art. no. S4.
[7]
K. I. Bos, V. J. Schuenemann, G. B. Golding, H. A. Burbano, N. Waglechner, B. K. Coombes, J. B. McPhee, S. N. DeWitte, M. Meyer, S. Schmedeset al., "A draft genome of Yersinia pestis from victims of the Black Death," Nature, vol. 478, no. 7370, pp. 506-510, 2011.
[8]
L. Orlando, A. Ginolhac, G. Zhang, D. Froese, A. Albrechtsen, M. Stiller, M. Schubert, E. Cappellini, B. Petersen, I. Moltke, et al., "Recalibrating Equus evolution using the genome sequence of an early Middle Pleistocene horse," Nature, vol. 499, pp. 74-78, 2013.
[9]
M. D. Martin, E. Cappellini, J. A. Samaniego, M. L. Zepeda, P. F. Campos, A. Seguin-Orlando, N. Wales, L. Orlando, S. Y. W. Ho, F. S. Dietrich, et al., "Reconstructing genome evolution in historic samples of the Irish potato famine pathogen," Nature Commun., vol. 4, 2013, Art. no. 2172.
[10]
V. J. Schuenemann, P. Singh, T. A. Mendum, B. Krause-Kyora, G. Jäger, K. I. Bos, A. Herbig, C. Economou, A. Benjak, P. Busso, et al., "Genome-wide comparison of medieval and modern Mycobacterium leprae," Sci., vol. 341, pp. 179-183, 2013.
[11]
M. Drancourt and D. Raoult, "Palaemicrobiology: Current issues and perspectives," Nature Rev. Microbiol., vol. 3, pp. 23-35, 2005.
[12]
A. Rajaraman, E. Tannier, and C. Chauve, "FPSAC: Fast phylogenetic scaffolding of ancient contigs," Bioinf., vol. 29, no. 23, pp. 2987-2994, 2013.
[13]
J. Ma?uch, M. Patterson, R. Wittler, C. Chauve, and E. Tannier, "Linearization of ancestral multichromosomal genomes," BMC Bioinf., vol. 13, no. Suppl 19, 2012, Art. no. S11.
[14]
E. Tannier, C. Zheng, and D. Sankoff, "Multichromosomal median and halving problems under different genomic distances," BMC Bioinf., vol. 10, no. 1, 2009, Art. no. 120.
[15]
P. Feijão and J. Meidanis, "SCJ: A breakpoint-like distance that simplifies several rearrangement problems," IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 8, no. 5, pp. 1318-1329, Sep./Oct. 2011.
[16]
N. Luhmann, M. Lafond, A. Thevenin, A. Ouangraoua, R. Wittler, and C. Chauve, "The SCJ small parsimony problem for weighted gene adjacencies," IEEE/ACM Trans. Comput. Biol. Bioinf., to be published.
[17]
N. Luhmann, C. Chauve, J. Stoye, and R. Wittler, "Scaffolding of ancient contigs and ancestral reconstruction in a phylogenetic framework," in Proc. Brazilian Symp. Bioinf., 2014, pp. 135-143.
[18]
W. M. Fitch, "Toward defining the course of evolution: Minimum change for a specific tree topology," Systematic Biol., vol. 20, no. 4, pp. 406-416, 1971.
[19]
D. Sankoff and P. Rousseau, "Locating the vertices of a Steiner tree in an arbitrary metric space," Math. Program., vol. 9, no. 1, pp. 240-246, 1975.
[20]
M. Cs?rös, "How to infer ancestral genome features by parsimony: Dynamic programming over an evolutionary tree," in Proc. Models Algorithms Genome Evolution, 2013, pp. 29-45.
[21]
V. Deshpande, E. D. Fung, S. Pham, and V. Bafna, "Cerulean: A hybrid assembly using high throughput short and long reads," in Proc. Int. Workshop Algorithms Bioinf., 2013, pp. 349-363.
[22]
N. Luhmann, D. Doerr, and C. Chauve, "Comparative scaffolding and gap filling of ancient bacterial genomes applied to two ancient yersinia pestis genomes," Microbial Genomics, vol. 3, no. 9, 2017, Art. no. e000123.
[23]
P. Biller, P. Feijão, and J. Meidanis, "Rearrangement-based phylogeny using the single-cut-or-join operation," IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 10, no. 1, pp. 122-134, Jan.-Mar. 2013.
[24]
J. T. Simpson, K. Wong, S. D. Jackman, J. E. Schein, S. J. Jones, and I. Birol, "ABySS: A parallel assembler for short read sequence data," Genome Res., vol. 19, no. 6, pp. 1117-1123, 2009.
[25]
M. Kolmogorov, B. Raney, B. Paten, and S. Pham, "Ragout--A reference-assisted assembly tool for bacterial genomes," Bioinf., vol. 30, no. 12, pp. i302-i309, 2014.
- Scaffolding of Ancient Contigs and Ancestral Reconstruction in a Phylogenetic Framework
Recommendations
Scaffolding pre-assembled contigs using SSPACE
Summary: De novo assembly tools play a main role in reconstructing genomes from next-generation sequencing (NGS) data and usually yield a number of contigs. Using paired-read sequencing data it is possible to assess the order, distance and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2018.
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 November 2018
Published in TCBB Volume 15, Issue 6
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 23Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 04 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in