While predicting 3D structure of a protein through homology modelling, the most important step is Multiple Sequence Alignment of template sequences with the target protein whose 3D model is to be predicted. At this step according to my book for Multiple Sequence Alignment, the either T-coffee or Praline software is used; these programs are heuristic in nature and based on a progressive alignment method. There are always concerns regarding the sensitivity and specificity of heuristic algorithms.

To avoid that problem I imagine one option is to use exhaustive algorithms. During this alignment step, which is very critical in 3D modelling, can we use exhaustive algorithms to yield good models?

  • $\begingroup$ Which exhaustive algorithms are you talking about? Finding the right homolog is, AKAIK, an NP-complete problem and that's why heuristic methods are used. $\endgroup$
    Commented Feb 16, 2016 at 5:48
  • $\begingroup$ I am talking about Dynamic programming modeling as it is exhaustive. $\endgroup$ Commented Feb 16, 2016 at 6:41
  • $\begingroup$ @WYSIWYG can you explain your answer please, so that I can develop better understanding. $\endgroup$ Commented Feb 16, 2016 at 6:44
  • 1
    $\begingroup$ Heuristic/greedy algorithms are faster than DP. I am not an expert in computer science to explain this in detail. You can have a look at this SO post. $\endgroup$
    Commented Feb 16, 2016 at 6:45

1 Answer 1



Methods for multiple sequence alignment (MSA) like T-coffee, which you mention, and Clustal (http://www.clustal.org), which is also widely used, employ heuristics for the alignment for the very good reason that exhaustive algorithms to do this are NP-complete.

You mention the dynamic programing algorithm as exhaustive in your comment. Alignment of two sequences by dynamic programming has an order of time complexity (big O) of $n^2$ and may take a few minutes depending on sequence length etc. Alignment of three has a big O of $n^3$ and can be done if you have lots of time on your hands, but it should be obvious that that's the limit to the number of sequences that can be aligned using dynamic programming.

There's no shame in heuristics. Perhaps the most widely used bioinformatics program in the world, BLAST, employs a heuristic. (And your brain makes decisions that your life depends on every day using heuristics.)

The methods that use heuristics for MSA have been successively modified to deal with known factors that can cause problems, so often they perform very well. How can you tell? What you need to do in using MSA programs is to perform a "sanity check" on any alignment that the programs produce — does it look reasonable, has it matched up similar regions well or are there vast gaps introduced or obvious regions of homology missed. And if you are doing 3D modeling and you don't get an alignment that looks good, then your modelling isn't likely to work.

Finally you always have to consider the possibility that there aren't any proteins of known structure that are similar to the one you want to model so you'll never get a good MSA.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .