[alephnil]

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...

[dalke]

Yes, for pairwise sequence alignment. The globally optimized multiple sequence alignment problem is NP-complete.