Sunday Morning Insight: Crossing into P territory

This is a follow-up to the recent  Sunday Morning Insight on Escaping Feynman's NP-Hard "Map of a Cat": Genomic Sequencing Edition

 

To recap, in compressive sensing, it's been known for a while that some solutions can be found thanks to l_1 (P or Polynomial time) relaxation of combinatorial problems (NP). In fact, the whole field of compressive sensing took off when people realized one could be on the P side most of the time.

In genome sequencing the latest long read technology have enabled the whole field to transport itself  from an NP territory into one where polynomial-time algorithms (P) will do OK. The threshold to cross is about 2K. Here is what we can read from the PacBio technology

Today PacBio released sequence data & results using its new P6-C4 chemistry: >14k average read length in C. elegans: http://t.co/KETvKFZ1eH
— R. Taylor Raborn (@rtraborn) October 15, 2014

When you go in P territory, many things change, here is one:

@sergekoren reduced drosophila assembly from 600,000cpu hours down to ~1000cpu hours using MHAP. #pacbio #pacbioUGM
— Kevin Corcoran (@kc31958) October 16, 2014

and here is what people say about the Oxford Nanopore technology.

   

Figure; From Model Selection with Many More Variables than Observations, presentation by Victoria Stodden

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.