Linearization of Median Genomes Under the Double-Cut-and-Join-Indel Model. (June 2019)

• Record Type: Journal Article
• Authors: Avdeyev, Pavel; Jiang, Shuai; Alekseyev, Max A
• Is Part Of: Evolutionary bioinformatics online. Volume 15(2019)
• Publication Date: 2019-06
• Subjects: Double cut and join -- indels -- genome median problem -- circular chromosome; Bioinformatics -- Periodicals; Evolutionary computation -- Periodicals; Genetic programming (Computer science) -- Periodicals; Computational Biology; Evolution, Molecular; Bioinformatics; Electronic journals; Periodicals; Fulltext; Internet Resources; Periodicals; Periodicals; 576.8
• DOI: 10.1177/1176934318820534
• Languages: English
• ISSNs: 1176-9343

Abstract

Reconstruction of the median genome consisting of linear chromosomes from three given genomes is known to be intractable. There exist efficient methods for solving a relaxed version of this problem, where the median genome is allowed to have circular chromosomes. We propose a method for construction of an approximate solution to the original problem from a solution to the relaxed problem and prove a bound on its approximation error. Our method also provides insights into the combinatorial structure of genome transformations with respect to appearance of circular chromosomes.