More Web Proxy on the site http://driver.im/

Article

Estimating true evolutionary distances between genomes

Authors:

Tandy WarnowAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 637 - 646

https://doi.org/10.1145/380752.380861

Published: 06 July 2001 Publication History

Abstract

Evolution operates on whole genomes by operations that change the order and strandedness of genes within the genomes. This type of data presents new opportunities for discoveries about deep evolutionary rearrangement events, provided that sufficiently accurate methods can be developed to reconstruct evolutionary trees in these models [3, 6, 7, 15, 17]. A necessary component of any such method is the ability to accurately estimate true evolutionary distances between two genomes, which is the number of rearrangement events that took place in the evolutionary history between them. We present a new technique called IEBP, for estimating the true evolutionary distance between two genomes, whether signed or unsigned, circular or linear, and for any relative probabilities of rearrangement event classes. The method is highly accurate, as our simulation study shows. This simulation study also shows that the distance estimation technique improves the accuracy of the phylogenetic trees reconstructed by the popular distance-based method, neighbor joining [1, 20].

References

[1]

K. Atteson. The performance of the neighbor-joining methods of phylogenetic reconstruction. Algorithmica, 25(2/3):251-278, 1999.]]

[2]

D. Bader, B. Moret, and M. Yan. A fast linear-time algorithm for inversion distance with an experimental comparison. In Proc. 7th Workshop on Algs. and Data Structures. (WADS 2001), 2001. To appear.]]

Digital Library

[3]

M. Blanchette, G. Bourque, and D. Sankoff. Breakpoint phylogenies. In S. Miyano and T. Takagi, editors, Genome Informatics, pages 25-34. Univ. Academy Press, 1997.]]

[4]

M. Blanchette, M. Kunisawa, and D. Sankoff. Gene order breakpoint evidence in animal mitochondrial phylogeny. J. Mol. Evol., 49:193-203, 1999.]]

[5]

A. Caprara and G. Lancia. Experimental and statistical analysis of sorting by reversals. In D. Sankoff and J. Nadeau, editors, Comparative Genomics, pages 171-184. Kluwer Academic Publishers, 2000.]]

[6]

Workshop on Gene Order Dynamics, Comparative Maps and Multigene Families (DCAF). Montreal, Canada, August 2000.]]

[7]

S. Downie and J. Palmer. Use of chloroplast DNA rearrangements in reconstructing plant phylogeny. In P. Soltis, D. Soltis, and J. Doyle, editors, Molecular Systematics of Plants, volume 49, pages 14-35. Chapman & Hall, 1992.]]

[8]

O. Gascuel. Personal communication, April 2001.]]

[9]

S. Hannenhalli and P. Pevzner. Transforming cabbage into turnip (polynomial algorithm for genomic distance problems). In Proc. 27th Annual ACM Symp. on Theory of Comp. (STOC95), pages 178-189. ACM Press, NY, 1995.]]

Digital Library

[10]

D. Huson, S. Nettles, K. Rice, T. Warnow, and S. Yooseph. The hybrid tree reconstruction method. J. Experimental Algorithmics, 4:178-189, 1999. http://www.jea.acm.org/.]]

Digital Library

[11]

R. Jansen. personal communication, October 3 2000.]]

[12]

H. Kaplan, R. Shamir, and R. Tarjan. Faster and simpler algorithm for sorting signed permutations by reversals. In Proc. 8th Annual Symp. on Discrete Alg. (SODA97), pages 344-351. ACM Press, NY, 1997.]]

Digital Library

[13]

S. Kumar. Minimum evolution trees. Mol. Biol. Evol., 15:584-593, 1996.]]

[14]

B. Moret, L.-S. Wang, T. Warnow, and S. Wyman. New approaches for reconstructing phylogenies based on gene order. In Proc. 9th Intl. Conf. on Intel. Sys. for Mol. Bio. (ISMB 2001). AAAI Press, 2001. To appear.]]

[15]

B. Moret, S. Wyman, D. Bader, T. Warnow, and M. Yan. A new implementation and detailed study of breakpoint analysis. In Proc. 6th Pacific Symp. Biocomputing (PSB 2001), pages 583-594, 2001.]]

[16]

J. Nadeau and B. Taylor. Lengths of chromosome segments conserved since divergence of man and mouse. Proc. Nat'l Acad. Sci. USA, 81:814-818, 1984.]]

[17]

R. Olmstead and J. Palmer. Chloroplast DNA systematics: a review of methods and data analysis. Amer. J. Bot., 81:1205-1224, 1994.]]

[18]

J. Palmer. Chloroplast and mitochondrial genome evolution in land plants. In R. Herrmann, editor, Cell Organelles, pages 99-133. Wein, 1992.]]

[19]

L. Raubeson and R. Jansen. Chloroplast DNA evidence on the ancient evolutionary split in vascular land plants. Science, 255:1697-1699, 1992.]]

[20]

N. Saitou and M. Nei. The neighbor-joining method: A new method for reconstructing phylogenetic trees. Mol. Biol. & Evol., 4:406-425, 1987.]]

[21]

D. Sankoff and M. Blanchette. Probability modelsfor genome rearrangements and linear invariants for phylogenetic inference. Proc. 3rd Int'l Conf. on Comput. Mol. Bio. (RECOMB99), pages 302-309, 1999.]]

Digital Library

[22]

D. Swofford, G. Olson, P. Waddell, and D. Hillis. Phylogenetic inference. In D. Hillis, C. Moritz, and B. Mable, editors, Molecular Systematics, Chapter 11. Sinauer Associates Inc, Second edition, 1996.]]

Cited By

Snir SWolf YBrezner SKoonin ESteel M(2024)On the Distribution of Synteny Blocks Under a Neutral Model of Genome DynamicsComparative Genomics10.1007/978-3-031-58072-7_9(173-188)Online publication date: 15-Apr-2024
https://doi.org/10.1007/978-3-031-58072-7_9
Zabelkin AAvdeyev PAlexeev N(2023)TruEst: a better estimator of evolutionary distance under the INFER modelJournal of Mathematical Biology10.1007/s00285-023-01955-z87:2Online publication date: 10-Jul-2023
https://doi.org/10.1007/s00285-023-01955-z
Katriel GMahanaymi UKoutschan CZeilberger DSteel MSnir S(2023)Using Generating Functions to Prove Additivity of Gene-Neighborhood Based Phylogenetics - Extended AbstractBioinformatics Research and Applications10.1007/978-981-99-7074-2_10(120-135)Online publication date: 8-Oct-2023
https://doi.org/10.1007/978-981-99-7074-2_10
Show More Cited By

Index Terms

Estimating true evolutionary distances between genomes

Recommendations

Estimating true evolutionary distances under the DCJ model

Motivation: Modern techniques can yield the ordering and strandedness of genes on each chromosome of a genome; such data already exists for hundreds of organisms. The evolutionary mechanisms through which the set of the genes of an organism is altered ...
Approximating the true evolutionary distance between two genomes

As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, duplications, deletions, and movements of genes ...
Efficient estimation of pairwise distances between genomes

Motivation: Genome comparison is central to contemporary genomics and typically relies on sequence alignment. However, genome-wide alignments are difficult to compute. We have, therefore, recently developed an accurate alignment-free estimator of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
22
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Snir SWolf YBrezner SKoonin ESteel M(2024)On the Distribution of Synteny Blocks Under a Neutral Model of Genome DynamicsComparative Genomics10.1007/978-3-031-58072-7_9(173-188)Online publication date: 15-Apr-2024
https://doi.org/10.1007/978-3-031-58072-7_9
Zabelkin AAvdeyev PAlexeev N(2023)TruEst: a better estimator of evolutionary distance under the INFER modelJournal of Mathematical Biology10.1007/s00285-023-01955-z87:2Online publication date: 10-Jul-2023
https://doi.org/10.1007/s00285-023-01955-z
Katriel GMahanaymi UKoutschan CZeilberger DSteel MSnir S(2023)Using Generating Functions to Prove Additivity of Gene-Neighborhood Based Phylogenetics - Extended AbstractBioinformatics Research and Applications10.1007/978-981-99-7074-2_10(120-135)Online publication date: 8-Oct-2023
https://doi.org/10.1007/978-981-99-7074-2_10
Xia RLin YZhou JGeng TBing FTang J(2018)Phylogenetic Reconstruction for Copy-Number Evolution ProblemsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2018.2829698(1-1)Online publication date: 2018
https://doi.org/10.1109/TCBB.2018.2829698
Zabelkin AAlexeev N(2018)Estimation of the True Evolutionary Distance Under the INFER ModelComparative Genomics10.1007/978-3-030-00834-5_4(72-87)Online publication date: 8-Sep-2018
https://doi.org/10.1007/978-3-030-00834-5_4
Biller PGuéguen LKnibbe CTannier E(2016)Breaking Good: Accounting for Fragility of Genomic Regions in Rearrangement Distance EstimationGenome Biology and Evolution10.1093/gbe/evw0838:5(1427-1439)Online publication date: 10-May-2016
https://doi.org/10.1093/gbe/evw083
Reidys CYu Jin E(2014)The evolution of the random reversal graphApplied Mathematics and Computation10.5555/2745044.2745074227:C(347-358)Online publication date: 15-Jan-2014
https://dl.acm.org/doi/10.5555/2745044.2745074
Reidys CYu Jin E(2014)The evolution of the random reversal graphApplied Mathematics and Computation10.1016/j.amc.2013.11.046227(347-358)Online publication date: Jan-2014
https://doi.org/10.1016/j.amc.2013.11.046
Moret BLin YTang J(2013)Rearrangements in Phylogenetic Inference: Compare, Model, or Encode?Models and Algorithms for Genome Evolution10.1007/978-1-4471-5298-9_7(147-171)Online publication date: 2013
https://doi.org/10.1007/978-1-4471-5298-9_7
Lin YRajan VMoret B(2012)Bootstrapping phylogenies inferred from rearrangement dataAlgorithms for Molecular Biology10.1186/1748-7188-7-217:1Online publication date: 29-Aug-2012
https://doi.org/10.1186/1748-7188-7-21
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents