Format

Send to

Choose Destination
Mol Biol (Mosk). 2015 May-Jun;49(3):372-83. doi: 10.7868/S0026898415030076.

[Rearrangement and inference of chromosome structures].

[Article in Russian]

Author information

1
Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, 127051 Russia.
2
lyubetsk@iitp.ru.

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.

KEYWORDS:

ancestral structure; chromosome rearrangement; chromosome structure; effective exact algorithm; evolution along a species tree; parsimony; parsimonyalong a species tree; species tree

PMID:
26107890
DOI:
10.7868/S0026898415030076
[Indexed for MEDLINE]
Free full text

Supplemental Content

Full text links

Icon for Molekuliarnaia biologiia
Loading ...
Support Center