<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

Publié en ligne: 01 nov. 2019

Pages: 1 - 13

Reçu: 05 mai 2018

Accepté: 18 juil. 2019

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

Mots clés
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

Publié en ligne: 01 nov. 2019

Pages: 1 - 13

Reçu: 05 mai 2018

Accepté: 18 juil. 2019

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

Mots cléspermutation 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.

Mots clés
permutation statistic, genome rearrangement, transposition distance