EUVIMEDEUVIMED entdecken
Crossref

Approximate strip exchanging

Swapnoneel Roy, Ashok Kumar Thakur

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).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsGene RearrangementModels, GeneticComputational BiologyComputer SimulationGenome

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}
}
Kostenlos starten →