Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Asymptotic medians of random permutations sampled from reversal random walks
Jamshidpey A., Sankoff D. Theoretical Computer Science698  9-13,2017.Type:Article
Date Reviewed: Feb 15 2018

The area of application of this interesting, and quite advanced, five-page paper is in the study of genomics and chromosomal rearrangements. The median specified in the title “is a point whose sum of distances to k given points [as defined in a metric space] is minimized,” the distance (metric) being the minimum number of permutation-reversals that transform one genome into another.

The reversals are realized as reversal random walks on the signed permutation group of n genes, with different time-scales among the k random walks. (Each gene in [1, . . ., n] has a bivalued sign denoting its orientation in the genome, hence the signed permutation group.) Given the starting-point median, the paper shows, building on the authors’ and others’ previous work, “how to find the relative positions of all the other medians.” This reduces the search-space of this NP-hard problem substantially, the search being among all possible positions of k reversal random walk samples. The authors prove theorems to the effect that the volume of the search-space is reduced by a factor of (2n × n!). The paper states, plausibly, that “reducing the search-space to a much smaller subdomain would be a significant help in practice.”

Reading a paper outside one’s specialty can be very rewarding, as has been the case for me here. One salutary effect is the invaluable experience of seeing working instances of all the “abstract stuff,” such as metric spaces, specific metrics, and the permutation group (and its signed enhancement), that one has previously been exposed to top-down, that is, abstractions-first. Another is the realization of Nobelist (and a founder of genomics) James D. Watson’s exhortation for us to “read around [our] subject ” [1].

The target audience of this advanced, well-written, and well-structured work is clearly experts in comparative genomics, of whom I am not one. I nevertheless found this work to be an informative exemplar of DNA computing [2] and recommend it to experts and laypersons alike.

Reviewer:  George Hacken Review #: CR145856 (1805-0240)
1) Watson, J. D. Avoid boring people. Alfred A. Knopf, New York, NY, 2007.
2) Rozenberg, G.; Salomaa, A. Handbook of formal languages (vol. 1). Springer, New York, NY, 1997.
Bookmark and Share
  Featured Reviewer  
 
Permutations And Combinations (G.2.1 ... )
 
 
Random Number Generation (G.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Permutations And Combinations": Date
Computing short generator sequences
Driscoll J., Furst M. Information and Computation 72(2): 117-132, 1987. Type: Article
Jan 1 1988
Permutations of bounded degree generate groups of polynomial diameter
McKenzie P. (ed) Information Processing Letters 19(5): 253-254, 1984. Type: Article
Aug 1 1985
How to construct pseudorandom permutations from pseudorandom functions
Luby M. (ed), Rackoff C. SIAM Journal on Computing 17(2): 373-386, 1988. Type: Article
Jul 1 1989
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