A New Implementation and Detailed Study of Breakpoint Analysis
2000; Springer Nature; Linguagem: Inglês
10.1142/9789814447362_0056
ISSN1571-4861
AutoresBernard M. E. Moret, David A. Bader, Stacia K. Wyman, Tandy Warnow, Mi Yan,
Tópico(s)Algorithms and Data Compression
ResumoBiocomputing 2001, pp. 583-594 (2000) No AccessA New Implementation and Detailed Study of Breakpoint AnalysisBernard M. E. Moret, David A. Bader, Stacia Wyman, Tandy Warnow, and Mi YanBernard M. E. MoretDept. of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA, David A. BaderDept. of Electrical & Computer Engineering, University of New Mexico, Albuquerque, NM 87131, USA, Stacia WymanDept. of Computer Science, University of Texas Austin, TX 78712, USA, Tandy WarnowDept. of Computer Science, University of Texas Austin, TX 78712, USA, and Mi YanDept. of Electrical & Computer Engineering, University of New Mexico, Albuquerque, NM 87131, USAhttps://doi.org/10.1142/9789814447362_0056Cited by:25 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: Phytogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions. One method is breakpoint analysis, developed by Blanchette and Sankoff 2 for solving the "breakpoint phylogeny." Our earlier studies 5,6 confirmed the usefulness of this approach, but also found that BPAnalysis, the implementation developed by Sankoff and Blanchette, was too slow to use on all but very small datasets. We report here on a reimplementation of BPAnalysis using the principles of algorithmic engineering. Our faster (by 2 to 3 orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had so far been considered out of reach. We report on these findings and also discuss future directions for our new implementation. FiguresReferencesRelatedDetailsCited By 25Synteny footprints provide clearer phylogenetic signal than sequence data for prokaryotic classificationGur Sevillya and Sagi Snir1 Jul 2019 | Molecular Phylogenetics and Evolution, Vol. 136Gene Family Evolution—An Algorithmic FrameworkNadia El-Mabrouk and Emmanuel Noutahi9 April 2019Ancestral reconstruction under weighted maximum matchingLingxi Zhou, William Hoskins, Jieyi Zhao and Jijun Tang1 Nov 2015Maximum likelihood phylogenetic reconstruction using gene order encodings Fei Hu, Nan Gao, Meng Zhang and Jijun Tang1 Apr 2011Complete nucleotide sequences of mitochondrial genomes of two solitary entoprocts, Loxocorone allax and Loxosomella aloxiata: Implications for lophotrochozoan phylogenyShin-ichi Yokobori, Tohru Iseto, Shuichi Asakawa, Takashi Sasaki and Nobuyoshi Shimizu et al.1 May 2008 | Molecular Phylogenetics and Evolution, Vol. 47, No. 2Engineering Algorithms for Computational BiologyDavid A. Bader1 Jan 2008An algorithm for reversal median problemJianxiu Hao27 July 2006 | Journal of Mathematical Chemistry, Vol. 42, No. 4FPGA Acceleration of Gene Rearrangement AnalysisJason D. Bakos1 Apr 2007High-performance Computing Methods for Computational Genomics1 Jan 2007Models and Methods in Comparative GenomicsGuillaume Bourque and Louxin Zhang1 Jan 2006Computational Grand Challenges in Assembling the Tree of Life: Problems and SolutionsDavid A. Bader, Usman Roshan and Alexandros Stamatakis1 Jan 2006High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational BiologyDavid A. Bader1 Jan 2005Mammalian phylogenomics comes of ageWilliam J. Murphy, Pavel A. Pevzner and Stephen J. O'Brien1 Dec 2004 | Trends in Genetics, Vol. 20, No. 12Reconstructing the Genomic Architecture of Ancestral Mammals: Lessons From Human, Mouse, and Rat GenomesGuillaume Bourque, Pavel A. Pevzner and Glenn Tesler1 April 2004 | Genome Research, Vol. 14, No. 4Reconstructing Ancestral Gene Orders Using Conserved IntervalsAnne Bergeron, Mathieu Blanchette, Annie Chateau and Cedric Chauve1 Jan 2004Steps toward accurate reconstructions of phylogenies from gene-order dataBernard M.E. Moret, Jijun Tang, Li-San Wang and Tandy Warnow1 Nov 2002 | Journal of Computer and System Sciences, Vol. 65, No. 3Efficient algorithms for multichromosomal genome rearrangementsGlenn Tesler1 Nov 2002 | Journal of Computer and System Sciences, Vol. 65, No. 3Inversion Medians Outperform Breakpoint Medians in Phylogeny Reconstruction from Gene-Order DataBernard M. E. Moret, Adam C. Siepel, Jijun Tang and Tao Liu10 October 2002Parameterized ComplexityMichael R. Fellows1 Jan 2002 | Electronic Notes in Theoretical Computer Science, Vol. 61A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental StudyDavid A. Bader, Bernard M. E. Moret and Mi Yan2 August 2001Exact-IEBP: A New Technique for Estimating Evolutionary Distances between Whole GenomesLi-San Wang17 August 2001Finding an Optimal Inversion Median: Experimental ResultsAdam C. Siepel and Bernard M. E. Moret17 August 2001On the Practical Solution of the Reversal Median ProblemAlberto Caprara17 August 2001Parameterized Complexity: The Main Ideas and Some Research FrontiersMichael R. Fellows4 December 2001Recovering True Rearrangement Events on Phylogenetic TreesHao Zhao and Guillaume Bourque Biocomputing 2001Metrics History PDF download
Referência(s)