Fast ancestral gene order reconstruction of genomes with unequal gene content

Feijão P, Soares de Araujo FE (2016)
BMC Bioinformatics 17(S14): 413.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 849.41 KB
Abstract / Bemerkung
Background During evolution, genomes are modified by large scale structural events, such as rearrangements, deletions or insertions of large blocks of DNA. Of particular interest, in order to better understand how this type of genomic evolution happens, is the reconstruction of ancestral genomes, given a phylogenetic tree with extant genomes at its leaves. One way of solving this problem is to assume a rearrangement model, such as Double Cut and Join (DCJ), and find a set of ancestral genomes that minimizes the number of events on the input tree. Since this problem is NP-hard for most rearrangement models, exact solutions are practical only for small instances, and heuristics have to be used for larger datasets. This type of approach can be called event-based. Another common approach is based on finding conserved structures between the input genomes, such as adjacencies between genes, possibly also assigning weights that indicate a measure of confidence or probability that this particular structure is present on each ancestral genome, and then finding a set of non conflicting adjacencies that optimize some given function, usually trying to maximize total weight and minimizing character changes in the tree. We call this type of methods homology-based. Results In previous work, we proposed an ancestral reconstruction method that combines homology- and event-based ideas, using the concept of intermediate genomes, that arise in DCJ rearrangement scenarios. This method showed better rate of correctly reconstructed adjacencies than other methods, while also being faster, since the use of intermediate genomes greatly reduces the search space. Here, we generalize the intermediate genome concept to genomes with unequal gene content, extending our method to account for gene insertions and deletions of any length. In many of the simulated datasets, our proposed method had better results than MLGO and MGRA, two state-of-the-art algorithms for ancestral reconstruction with unequal gene content, while running much faster, making it more scalable to larger datasets. Conclusion Studing ancestral reconstruction problems under a new light, using the concept of intermediate genomes, allows the design of very fast algorithms by greatly reducing the solution search space, while also giving very good results. The algorithms introduced in this paper were implemented in an open-source software called RINGO (ancestral Reconstruction with INtermediate GenOmes), available at https://github.com/pedrofeijao/RINGO.
Stichworte
Ancestral reconstruction Small parsimony problem Genome rearrangement Double-cut-and-join InDels Gene insertions and deletions
Erscheinungsjahr
2016
Zeitschriftentitel
BMC Bioinformatics
Band
17
Ausgabe
S14
Art.-Nr.
413
Konferenz
14th Annual Research in Computational Molecular Biology (RECOMB) Comparative Genomics Satellite Workshop
Konferenzort
Montreal, Canada
Konferenzdatum
2016-10-11 – 2016-10-11
ISSN
1471-2105
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Deutsche Forschungsgemeinschaft und die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2907670

Zitieren

Feijão P, Soares de Araujo FE. Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinformatics. 2016;17(S14): 413.
Feijão, P., & Soares de Araujo, F. E. (2016). Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinformatics, 17(S14), 413. doi:10.1186/s12859-016-1261-9
Feijão, Pedro, and Soares de Araujo, Francisco Eloi. 2016. “Fast ancestral gene order reconstruction of genomes with unequal gene content”. BMC Bioinformatics 17 (S14): 413.
Feijão, P., and Soares de Araujo, F. E. (2016). Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinformatics 17:413.
Feijão, P., & Soares de Araujo, F.E., 2016. Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinformatics, 17(S14): 413.
P. Feijão and F.E. Soares de Araujo, “Fast ancestral gene order reconstruction of genomes with unequal gene content”, BMC Bioinformatics, vol. 17, 2016, : 413.
Feijão, P., Soares de Araujo, F.E.: Fast ancestral gene order reconstruction of genomes with unequal gene content. BMC Bioinformatics. 17, : 413 (2016).
Feijão, Pedro, and Soares de Araujo, Francisco Eloi. “Fast ancestral gene order reconstruction of genomes with unequal gene content”. BMC Bioinformatics 17.S14 (2016): 413.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T09:18:42Z
MD5 Prüfsumme
43f568f744939d60b9e76c0661b4a079


26 References

Daten bereitgestellt von Europe PubMed Central.

Construction of phylogenetic trees.
Fitch WM, Margoliash E., Science 155(3760), 1967
PMID: 5334057
MLGO: phylogeny reconstruction and ancestral inference from gene-order data.
Hu F, Lin Y, Tang J., BMC Bioinformatics 15(), 2014
PMID: 25376663
On the PATHGROUPS approach to rapid small phylogeny.
Zheng C, Sankoff D., BMC Bioinformatics 12 Suppl 1(), 2011
PMID: 21342571
Reconstruction of ancestral gene orders using intermediate genomes.
Feijao P., BMC Bioinformatics 16 Suppl 14(), 2015
PMID: 26451811
Medians seek the corners, and other conjectures.
Haghighi M, Sankoff D., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281922
Breakpoint graphs and ancestral genome reconstructions.
Alekseyev MA, Pevzner PA., Genome Res. 19(5), 2009
PMID: 19218533
Rearrangement-based phylogeny using the Single-Cut-or-Join operation.
Biller P, Feijao P, Meidanis J., IEEE/ACM Trans Comput Biol Bioinform 10(1), 2013
PMID: 23702549
Evolution of genes neighborhood within reconciled phylogenies: an ensemble approach.
Chauve C, Ponty Y, Zanetti J., BMC Bioinformatics 16 Suppl 19(), 2015
PMID: 26696141
Genome-scale evolution: reconstructing gene orders in the ancestral species.
Bourque G, Pevzner PA., Genome Res. 12(1), 2002
PMID: 11779828
Reconstructing contiguous regions of an ancestral genome.
Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, Blanchette M, Haussler D, Miller W., Genome Res. 16(12), 2006
PMID: 16983148
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
ANGES: reconstructing ANcestral GEnomeS maps.
Jones BR, Rajaraman A, Tannier E, Chauve C., Bioinformatics 28(18), 2012
PMID: 22820205
An exact solver for the DCJ median problem.
Zhang M, Arndt W, Tang J., Pac Symp Biocomput (), 2009
PMID: 19209699
Probabilistic Reconstruction of Ancestral Gene Orders with Insertions and Deletions.
Hu F, Zhou J, Zhou L, Tang J., IEEE/ACM Trans Comput Biol Bioinform 11(4), 2014
PMID: 26356337
SCJ: a breakpoint-like distance that simplifies several rearrangement problems.
Feijao P, Meidanis J., IEEE/ACM Trans Comput Biol Bioinform 8(5), 2011
PMID: 21339538
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
A flexible ancestral genome reconstruction method based on gapped adjacencies.
Gagnon Y, Blanchette M, El-Mabrouk N., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281872
ProCARs: Progressive Reconstruction of Ancestral Gene Orders.
Perrin A, Varre JS, Blanquart S, Ouangraoua A., BMC Genomics 16 Suppl 5(), 2015
PMID: 26040958
DCJ-Indel sorting revisited.
Compeau PE., Algorithms Mol Biol 8(1), 2013
PMID: 23452758
A new implementation and detailed study of breakpoint analysis.
Moret BM, Wyman S, Bader DA, Warnow T, Yan M., Pac Symp Biocomput (), 2001
PMID: 11262975
Multichromosomal median and halving problems under different genomic distances.
Tannier E, Zheng C, Sankoff D., BMC Bioinformatics 10(), 2009
PMID: 19386099
Additive evolutionary trees.
Waterman MS, Smith TF, Singh M, Beyer WA., J. Theor. Biol. 64(2), 1977
PMID: 839800
The solution space of sorting by DCJ.
Braga MD, Stoye J., J. Comput. Biol. 17(9), 2010
PMID: 20874401
Reconstruction of Ancestral Genomes in Presence of Gene Gain and Loss.
Avdeyev P, Jiang S, Aganezov S, Hu F, Alekseyev MA., J. Comput. Biol. 23(3), 2016
PMID: 26885568
Multiple genome rearrangement and breakpoint phylogeny.
Sankoff D, Blanchette M., J. Comput. Biol. 5(3), 1998
PMID: 9773350
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Quellen

PMID: 28185578
PubMed | Europe PMC

Suchen in

Google Scholar