Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A new efficient algorithm for the all sorting reversals problem with no bad components
Wang B. IEEE/ACM Transactions on Computational Biology and Bioinformatics13 (4):599-609,2016.Type:Article
Date Reviewed: Jan 17 2017

The paradigm of Wang’s paper is computational biology, more specifically genome rearrangement. The genome rearrangement problem simply means changing one genome sequence to another in the shortest possible way.

There are several genome rearrangement problems in the literature. One that is widely studied is the all sorting reversal (ASR) problem, which is all about finding the shortest chain of reversals (evolutionary changes in species) that converts one chromosome into another.

For the ASR problem, Seipel proposed an algorithm that executes in cubic time complexity with bad components (which are certain typical structures). But bad components being unrealistic (God is not an antagonist!), Swenson and others improved it with an algorithm with quadratic runtime complexity. However, it has been recently observed that this improved algorithm does not work for all inputs. This motivated the author to build a more robust algorithm with the same quadratic worst-case complexity. Wang’s algorithm is linear with respect to input and output size. Since algorithms for detecting the bad components are available, it may be possible to combine Wang’s algorithm with Seipel’s algorithm to solve the general ASR problem in quadratic time in the average case. The paper is useful and will certainly draw some interest among researchers and postgraduates in computing science.

Reviewer:  Soubhik Chakraborty Review #: CR145001 (1705-0316)
Bookmark and Share
  Featured Reviewer  
 
Biology And Genetics (J.3 ... )
 
 
Algorithms (I.1.2 )
 
 
Numerical Analysis (G.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Biology And Genetics": Date
Discovering the secrets of DNA
Friedland P., Kedes L. Communications of the ACM 28(11): 1164-1186, 1985. Type: Article
May 1 1986
The formation of three-dimensional biological structures: computer uses and future needs
Levinthal C.  Computer culture: the scientific, intellectual, and social impact of the computer (, New York,1801984. Type: Proceedings
Sep 1 1986
Computer techniques in neuroanatomy
Capowski J., Plenum Press, New York, NY, 1989. Type: Book (9789780306432637)
Nov 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy