Expected genomic dissimilarity

• Main Authors: Chitturi, Bhadrachalam, Krishnaveni, K.S.
• Format: Conference Proceeding
• Language: English
• Subjects: Bioinformatics; Biological system modeling; block-moves; Computational modeling; evolutionary biology; Generators; Genomic distance; Genomics; NP-complete; Optimization; permutation group; Sorting
• ISSN: 2573-5276
• DOI: 10.1109/ICMSAO.2019.8880405

Permutation, a discrete structure, is a sequence over the corresponding alphabet Σ where every element of Σ occurs exactly once. The set of permutations over Σ forms a symmetric group denoted by S n . In evolutionary biology, permutation models a genome. If π = (π 1 , π 2 , π 3 ,..., π n ) is a permutation over Σ = {0, 1, ... ,n - 1} then π i , and π i +1 form an adjacency if π i +1 = π i , + 1, 0 ≤ i ≤ n-1. Various operations that model genomic mutations are defined over permutations. An operation is defined by a set of generators. Execution of a specific generator is a move. The distance between a pair of permutations α and ß under a given operation ⊕ is the minimum number of moves that are required to transform a into ß. It denotes genomic dissimilarity between a and ß. Computation of distance is intractable for various operations including transposition. We call prefix transposition, suffix transposition and transposition as block-moves. Based on properties of S n related to adjacencies we develop a model that estimates the expected block-move distance between any pair of permutations.