title: [Rearrangement and inference of chromosome structures].
abstract: The chromosome structure is defined as a set of chromosomes that consist of genes assigned to one of the DNA strands and represented in a circular or linear arrangement. A widely investigated problem is to define the shortest algorithmic path of chromosome rearrangements that transforms one chromosome structure into another. When equal rearrangement costs and constant gene content are considered, the solution to the problem is known. In this work, a principally novel approach was developed that presents an exact algorithm with linear time complexity for both equal and unequal costs, in which chromosome structures defined on the same set of genes were considered. In addition, to solve the problem of the inference of ancestral chromosome structures containing different sets of genes when the original structures are fixed in leaves, exact and heuristic algorithms were developed.
authors.affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, 127051 Russia.
authors.forename: K Yu
authors.initials: KY
authors.lastname: Gorbunov
authors.affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, 127051 Russia.
authors.forename: R A
authors.initials: RA
authors.lastname: Gershgorin
authors.affiliation: Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, 127051 Russia.|lyubetsk@iitp.ru.
authors.forename: V A
authors.initials: VA
authors.lastname: Lyubetsky
mesh_terms: D000465:Algorithms; D022004:Chromosome Structures; D019295:Computational Biology; D003198:Computer Simulation; D019143:Evolution, Molecular; D015321:Gene Rearrangement / Q000235:genetics*; D008957:Models, Genetic; D010802:Phylogeny; D017422:Sequence Analysis, DNA; D013816:Thermodynamics
keywords: ancestral structure; chromosome rearrangement; chromosome structure; effective exact algorithm; evolution along a species tree; parsimony; parsimonyalong a species tree; species tree