News for hackers. Stuff that matters.

A comment on A farewell to bioinformatics (2012). Parent comment

Re:A farewell to bioinformatics (2012) by alephnil on Sunday January 27, 2013 @11:19AM (#5124651)
It is far more difficult than sequence alignment. Sequence alignment has quadratic complexity, while fragment assembly is NP-hard. Se for example

http://scholar.google.com/scholar?cluster=131745416915434219...

[ Parent | on HN ]
Re:A farewell to bioinformatics (2012) by dalke on Sunday January 27, 2013 @06:15PM (#5126111)
Yes, for pairwise sequence alignment. The globally optimized multiple sequence alignment problem is NP-complete.
[ Parent | on HN ]