Approximate strip exchanging
International Journal of Computational Biology and Drug Design · 2008
DOI: 10.1504/ijcbdd.2008.018712 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Computational Biology and Drug Design, 2008. Verfasst von Swapnoneel Roy und 1 weiteren Autor:innen. Beteiligte Einrichtung: IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com. Hauptthemen laut MEDLINE: Algorithms, Gene Rearrangement, Models, Genetic. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
Genome rearrangements have been modelled by a variety of primitives such as reversals, transpositions, block moves and block interchanges. We consider such a genome rearrangement primitive Strip Exchanges. Given a permutation, the challenge is to sort it by using minimum number of strip exchanges. A strip exchanging move interchanges the positions of two chosen strips so that they merge with other strips. The strip exchange problem is to sort a permutation using minimum number of strip exchanges. We present here the first non-trivial 2-approximation algorithm to this problem. We also observe that sorting by strip-exchanges is fixed-parameter-tractable. Lastly we discuss the application of strip exchanges in a different area Optical Character Recognition (OCR) with an example.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com
Zitieren
APA
Roy, S., & Thakur, A. K. (2008). Approximate strip exchanging. International Journal of Computational Biology and Drug Design. https://doi.org/10.1504/ijcbdd.2008.018712
Vancouver
Roy S, Thakur AK. Approximate strip exchanging. International Journal of Computational Biology and Drug Design. 2008. doi:10.1504/ijcbdd.2008.018712
BibTeX
@article{Roy2008,
author = {Roy, Swapnoneel and Thakur, Ashok Kumar},
title = {Approximate strip exchanging},
journal = {International Journal of Computational Biology and Drug Design},
year = {2008},
doi = {10.1504/ijcbdd.2008.018712}
}
EUVIMED