<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Permutations are frequently used in solving the genome rearrangement problem, whose goal is finding the shortest sequence of mutations transforming one genome into another. We introduce the Deletion-Insertion model (DI) to model small-scale mutations in species with linear chromosomes, such as humans. Applying one restriction to this model, we obtain the transposition model for genome rearrangement, which was shown to be NP-hard in [4]. We use combinatorial reasoning and permutation statistics to develop a polynomial-time algorithm to approximate the minimum number of transpositions required in the transposition model and to analyze the sharpness of several bounds on transpositions between genomes.</p></abstract>

Permutations are frequently used in solving the genome rearrangement problem, whose goal is finding the shortest sequence of mutations transforming one genome into another. We introduce the Deletion-Insertion model (DI) to model small-scale mutations in species with linear chromosomes, such as humans. Applying one restriction to this model, we obtain the transposition model for genome rearrangement, which was shown to be NP-hard in [4]. We use combinatorial reasoning and permutation statistics to develop a polynomial-time algorithm to approximate the minimum number of transpositions required in the transposition model and to analyze the sharpness of several bounds on transpositions between genomes.

The Deletion-Insertion model applied to the genome rearrangement problem

Department of Mathematics, Rose-Hulman Institute of Technology

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"The Deletion-Insertion model applied to the genome rearrangement problem"}

Permutations are frequently used in solving the genome rearrangement problem, whose goal is finding the shortest sequence of mutations transforming one genome...

The Deletion-Insertion model applied to the genome rearrangement problem

Data publikacji: 01 lis 2019

Zakres stron: 1 - 13

Otrzymano: 05 maj 2018

Przyjęty: 18 lip 2019

DOI: https://doi.org/10.1515/puma-2015-0030

Słowa kluczowe
permutation statistic, genome rearrangement, transposition distance

© 2019 Abra Brisbin et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

The Deletion-Insertion model applied to the genome rearrangement problem

Data publikacji: 01 lis 2019

Zakres stron: 1 - 13

Otrzymano: 05 maj 2018

Przyjęty: 18 lip 2019

DOI: https://doi.org/10.1515/puma-2015-0030

Słowa kluczowepermutation statistic, genome rearrangement, transposition distance

© 2019 Abra Brisbin et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Słowa kluczowe
permutation statistic, genome rearrangement, transposition distance