標題: Sorting permutations by cut-circularize-linearize-and-paste operations
作者: Huang, Keng-Hsuan
Chen, Kun-Tze
Lu, Chin Lung
生物資訊及系統生物研究所
Institude of Bioinformatics and Systems Biology
公開日期: 30-Nov-2011
摘要: Background: Genome rearrangements are studied on the basis of genome-wide analysis of gene orders and important in the evolution of species. In the last two decades, a variety of rearrangement operations, such as reversals, transpositions, block-interchanges, translocations, fusions and fissions, have been proposed to evaluate the differences between gene orders in two or more genomes. Usually, the computational studies of genome rearrangements are formulated as problems of sorting permutations by rearrangement operations. Result: In this article, we study a sorting problem by cut-circularize-linearize-and-paste (CCLP) operations, which aims to find a minimum number of CCLP operations to sort a signed permutation representing a chromosome. The CCLP is a genome rearrangement operation that cuts a segment out of a chromosome, circularizes the segment into a temporary circle, linearizes the temporary circle as a linear segment, and possibly inverts the linearized segment and pastes it into the remaining chromosome. The CCLP operation can model many well-known rearrangements, such as reversals, transpositions and block-interchanges, and others not reported in the biological literature. In addition, it really occurs in the immune response of higher animals. To distinguish those CCLP operations from the reversal, we call them as non-reversal CCLP operations. In this study, we use permutation groups in algebra to design an O(delta n) time algorithm for solving the weighted sorting problem by CCLP operations when the weight ratio between reversals and non-reversal CCLP operations is 1:2, where n is the number of genes in the given chromosome and delta is the number of needed CCLP operations. Conclusion: The algorithm we propose in this study is very simple so that it can be easily implemented with 1-dimensional arrays and useful in the studies of phylogenetic tree reconstruction and human immune response to tumors.
URI: http://dx.doi.org/S26
http://hdl.handle.net/11536/15899
ISSN: 1471-2164
DOI: S26
期刊: BMC GENOMICS
Volume: 12
Issue: 
結束頁: 
Appears in Collections:Conferences Paper


Files in This Item:

  1. 000303447900006.pdf