nach oben

Network Modeling Analysis in Health Informatics and Bioinformatics

Erschienen in:

01.12.2016 | Original Article

New approximations for block sorting

verfasst von: J. Huang, S. Roy, A. Asaithambi

Erschienen in: Network Modeling Analysis in Health Informatics and Bioinformatics | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We develop, present, and analyze a simple, new 2-approximation algorithm for block sorting in which we use a newly introduced combinatorial structure called an ordered pair. Our algorithm achieves the best known approximation ratio of 2 , the tightest known upper bound in terms of the number of block moves needed for block sorting.

Vorheriger Artikel In silico vaccine design against type 1 diabetes based on molecular modeling of coxsackievirus B4 epitopes

Nächster Artikel Evaluation of associative classification-based multifactor dimensionality reduction in the presence of noise

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bafna V, Pavel PA (1998) Sorting by transpositions. SIAM J Discrete Math

Bafna V, Pevzner PA (1996) Genome rearrangements and sorting by reversals. SIAM J Comput 25(2):272–289. doi:10.1137/S0097539793250627 MathSciNetCrossRefMATH

Bein WW, Larmore LL, Latifi S, Sudborough IH (2003) Block sorting is hard. Int J Found Comput Sci 14(03):425–437MathSciNetCrossRefMATH

Bein WW, Larmore LL, Morales L, Sudborough IH (2009) A quadratic time 2-approximation algorithm for block sorting. Theor Comput Sci 410(8):711–717MathSciNetCrossRefMATH

Bulteau L, Fertin G, Rusu I (2001) Sorting by transpositions is difficult. In: Proceedings of the 38th international colloquim conference on automata, languages and programming—volume part I, ICALP’11. Springer, Berlin, pp 654–665. http://dl.acm.org/citation.cfm?id=2027127.2027197

Bulteau L, Fertin G, Rusu I (2012) Pancake flipping is hard. In: Proceedings of the 37th international conference on mathematical foundations of computer science, MFCS’12. Springer, Berlin, pp 247–258. doi:10.1007/978-3-642-32589-2_24

Caprara A (1997) Sorting by reversals is difficult. In: Proceedings of the first annual international conference on computational molecular biology, RECOMB ’97. ACM, New York, NY, USA, pp 75–83. doi:10.1145/267521.267531, http://doi.acm.org/10.1145/267521.267531

Christie D, Irving R (2001) Sorting strings by reversals and by transpositions. SIAM J Discrete Math 14(2):193–206. doi:10.1137/S0895480197331995 MathSciNetCrossRefMATH

Christie DA (1996) Sorting permutations by block-interchanges. Inf Process Lett 60(4):165–169MathSciNetCrossRefMATH

Christie DA (1999) Genome rearrangement problems. Ph.D. thesis

Elias I, Hartman T (2006) A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans Comput Biol Bioinform 3(4):369–379. doi:10.1109/TCBB.2006.44 CrossRef

Firoz JS, Hasan M, Khan AZ, Rahman MS (2011) The 1.375 approximation algorithm for sorting by transpositions can run in o (n log n) time. J Comput Biol 18(8):1007–1011MathSciNetCrossRefMATH

Gates WH, Papadimitriou CH (1979) Bounds for sorting by prefix reversal. Discrete Math 27(1):47–57MathSciNetCrossRefMATH

Gu QP, Peng S, Sudborough H (1999) A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor Comput Sci 210(2):327–339MathSciNetCrossRefMATH

Hannenhalli S, Pevzner PA (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 46(1):1–27. doi:10.1145/300515.300516. http://doi.acm.org/10.1145/300515.300516

Hartman T, Shamir R (2006) A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf Comput 204(2):275–290MathSciNetCrossRefMATH

Huang J, Roy S (2014) On sorting under special transpositions. In: 2014 IEEE international conference on bioinformatics and bioengineering (BIBE), pp 325–328

Lin YC, Lu CL, Chang HY, Tang CY (2005) An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species. J Comput Biol 12(1):102–112CrossRef

Mahajan M, Rama R, Raman V, Vijaykumar S (2006) Approximate block sorting. Int J Found Comput Sci 17(02):337–355MathSciNetCrossRefMATH

Mira C, Meidanis J (2007) Sorting by block-interchanges and signed reversals. In: Fourth International Conference on information technology, 2007, ITNG’07, pp 670–676

Narayanaswamy N, Roy S (2015) Block sorting is apx-hard. In: Algorithms and complexity. Springer, pp 377–389

Palmer JD, Herbon LA (1988) Plant mitochondrial dna evolved rapidly in structure, but slowly in sequence. J Mol Evol 28(1–2):87–97CrossRef

Titel: New approximations for block sorting
verfasst von: J. Huang
S. Roy
A. Asaithambi
Publikationsdatum: 01.12.2016
Verlag: Springer Vienna
Erschienen in: Network Modeling Analysis in Health Informatics and Bioinformatics / Ausgabe 1/2016
Print ISSN: 2192-6662
Elektronische ISSN: 2192-6670
DOI: https://doi.org/10.1007/s13721-016-0113-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Molecular modeling and simulation analysis of glaucoma pathway

Epitope prediction for MSP119 protein in Plasmodium yeolii using computational approaches

A new approach to distinguish migraine from stroke by mining structured and unstructured clinical data-sources

In silico designing of some agonists of toll-like receptor 5 as a novel vaccine adjuvant candidates

Evaluation of associative classification-based multifactor dimensionality reduction in the presence of noise

A holistic approach for integration of biological systems and usage in drug discovery