As somebody who has actually taught a university course in Analysis of Algorithms, I felt it may be good for me to give a "stab" at answering this one.

To begin, we must understand that programs and algorithms are not the same thing. One is an implementation, the other is a mathematical description. One is associated with a machine, the other with a computational model. Why do we care about analysis of algorithms? This question is trivial to answer. We care about having efficient algorithms in terms of time and space. The computational models at the present time reflect quite well (and very rarely not) the behaviour of an algorithm when it is implemented. Remember, the interest is in algorithms typically. We prove theorems and analyze algorithms, not their implementations.

So why would we care about this in software tools? As I said, computational models seem to be pretty accurate to how they perform (and often is of research interest to some). For example, the RAM model is extremely good for most cases in analyzing an algorithm in the worst-case. Typically we are interested in the behaviour of the algorithm in specific cases. Why would we care about this? Because, if we know the algorithm will have a certain asymptotic behaviour, then we know in the worst-case it cannot do any worse than that. The other factor to consider is asymptotics. If we know the behaviour as the input gets large, we have a better idea of how it will compare in complexity with other algorithms.

Not just in bioinformatics (which relies a lot on algorithms), but any area of Computing needs to consider algorithms as formal descriptions and ensuring they are correct and terminate with a certain time-complexity. These are not just "abstract ideas" that serve no purpose. They lay the ground work of almost everything we do in Theoretical Computer Science (core of CS) when it comes to Algorithms. Once you have time-complexities, we can compare algorithms, and even categorize them and ask questions about them. Many bioinformatics problems in particular can be NP-hard, so this will be even more important when considering an application.

Hope this helps!

The answer is quite simple. As a software developer you will not always implement new algorithms for companies or institutions. The regular case is that engineers need to understand, optimize and further develop existing solutions. This is exactly the value for which hiring companies pay their software engineers.

In addition, the field of bioinformatics is research-intensive and thrives on the development and improvement of algorithms.

This is quite a difficult question as traditional algorithms are becoming more difficult to apply multivariate functions to within a program. That is to say that if a function has 10 possible inputs and 100 possible outputs (including the evaluation within the function) it cannot be presented easily in traditional algorithmic notation. As Eldar noted above many older programs are presented in a simpler algorithmic method however these older programs are becoming bloated with additions and modifications making understanding them a long winded process of finding out which section is doing what. In a similar manner that analogue TV's eventually became too complicated and no one actually understood the maths and science behind every component.

As software development methods progress it would probably be a good idea for someone to come up with a new method for presenting how multivariate functions operate.

It is sometimes best to write algorithms from first principles rather than to modify a large computer program already written. The way to do this would be as follows. Go back to the original problem. Develop a paradigm for analysis. It may be along a similar line to what has been done before, or it may be a totally new approach. However, to make a good comparison, you should understand the existing algorithm thoroughly. That is one reason why analysis of existing algorithms is important. To understand the existing algorithm, you may need to analyze it piece by piece. Remember KISS - keep it simple stupid. If you have more than one degree of freedom, you cannot know what variable caused a certain result. So break the algorithm into components with one degree of freedom, then see what each does. Knowing well the algorithmic basis for the method, it may be possible to improve on it and develop an improved method.

Edward,

I don't know exactly about algorithms in bioinformatics software. However, as a specialist in fast algorithms, I can try to answer to the first part of your questions: "Why is analysis of algorithms important to the development of computational tools".

The analysis of algorithms, especially the estimation of the computational complexity, is very important, since we must know, how close we come to the limit of our possibilities in the speed to calculate a value of the function, integral, etc. The "physical(technical) restrictions" of a calculation on computer are possible to estimate. But there are also mathematical/algorithmical restrictions, what defined by computational complexity. So the analysis of algorithms helps us to navigate in, whether it's possible to increase the efficiency of computing.

As somebody who has actually taught a university course in Analysis of Algorithms, I felt it may be good for me to give a "stab" at answering this one.

To begin, we must understand that programs and algorithms are not the same thing. One is an implementation, the other is a mathematical description. One is associated with a machine, the other with a computational model. Why do we care about analysis of algorithms? This question is trivial to answer. We care about having efficient algorithms in terms of time and space. The computational models at the present time reflect quite well (and very rarely not) the behaviour of an algorithm when it is implemented. Remember, the interest is in algorithms typically. We prove theorems and analyze algorithms, not their implementations.

So why would we care about this in software tools? As I said, computational models seem to be pretty accurate to how they perform (and often is of research interest to some). For example, the RAM model is extremely good for most cases in analyzing an algorithm in the worst-case. Typically we are interested in the behaviour of the algorithm in specific cases. Why would we care about this? Because, if we know the algorithm will have a certain asymptotic behaviour, then we know in the worst-case it cannot do any worse than that. The other factor to consider is asymptotics. If we know the behaviour as the input gets large, we have a better idea of how it will compare in complexity with other algorithms.

Not just in bioinformatics (which relies a lot on algorithms), but any area of Computing needs to consider algorithms as formal descriptions and ensuring they are correct and terminate with a certain time-complexity. These are not just "abstract ideas" that serve no purpose. They lay the ground work of almost everything we do in Theoretical Computer Science (core of CS) when it comes to Algorithms. Once you have time-complexities, we can compare algorithms, and even categorize them and ask questions about them. Many bioinformatics problems in particular can be NP-hard, so this will be even more important when considering an application.

Hope this helps!

I think one of the fundamental and most important things is that it provides an standardized way of comparing different techniques without having to worry about implementation details. It allows you to compare the essence of the algorithm, show in which situation a specific method is useful and whether it's better or worse than other proposed solutions.

I think this question could be answered with an example: the Water or Needle algorithm could not be used for sequence database search, as its time complexity is too high, that is why we need BLAST, a faster algorithm, for database search.

Another example is in the alignment of protein coding DNA sequences, although the 64-state codon level alignment algorithm is in principle surperior than DNA or protein level alignment, it is rarely used in practice, because you have to wait a long time, especially when dealing with a large dataset, and the result is not as good as you expect, there might be some errors: errors will prone to occur in implementation of a complex algorithm more than in a simple one.

Analysis , is the most important step for software development . It concerns with "understanding" why and what the system do . No one can set an algorithm without profound understanding of problem and its solution.

if you need to develop bioinformatic software you need to have " understanding" in biology and the tools that apply on each rule of biological system .

Keep in mind that algorithms with worse time-complexity can out-perform theoretically better algorithms, because the latter can have huge constants and other overhead.

Brute force can be faster because real-life datasets are NOT infinite.

@Lambert. I think you mean large. Brute force methods on an infinite set would never terminate for some instances (assuming you are talking about search problems). Even then, this would vary from problem to problem. One needs to keep in mind the following:

-Constants will vary from problem to problem. Even then, they are constants as instances get large. Time-complexity focuses on when the input gets large. Constants don't change the behaviour as they are fixed or bounded by the input size.

-What is meant by "theoretically better algorithms". Your point relates to implementations of algorithms, not algorithms themselves. The architecture employing the implementation, and how one implements the algorithm will be crucial in evaluating its performance (which can be difference) on a computer which is an application. Most examples that fall into this category typically are those not well measured by the model of computation chosen. A splendid example is naive polynomial evaluations versus Horner's Method to evaluate a polynomial f at f(x), given some integer x. Though both will have the same time-complexity in the worst case, the number of multiplications by Horner's Method will be close to half compared to a naive approach and will as a consequence correspond to a better implementation. This is one reason why Horner's Method is often a handy algorithm, though one can do the analysis to count these basic operations. Why does this happen? Because, the RAM model counts the simple operations as inputs get large. This is an example of a flaw of the RAM model, and is often something I ensure my students know about, though it doesn't really come out commonly for more complex problems.

-Why would when inputs get large matter? Computational problems seem to be easier to compare when you let inputs be large. Why? The behaviour of an algorithm can be easier to spot when handling instances to solve that will "push" the algorithm. When different types of analysis, in particular, worst-case analysis are used, we throw instances that cause the worst behaviour and count the number of basic steps using a computational model. Any person who has tried to solve a problem with tiny examples will tell you first hand that playing with n=1, or n=2 isn't going to give much insight into the problem.

-We are interested in the asymptotic behaviour because we want to categorize and compare algorithms by their algorithmic complexity, not necessarily their performance. Why? Machines can vary from each other. This is why focusing on implementations is not the greatest of ideas when looking at algorithms but is worth exploring if one wants to use them on particular systems or architectures. That's why one a new architecture is coming out, you see many classic computational problems attacked on it first to ensure it can be used, then benchmarks are set up to employ pragmatic but difficult problems (typically NP-hard optimization problems). The focus on computational model is vital for this purpose. It means mathematically I can test the quality of an algorithm in terms of time and space without even needing to implement it. If one is of course interested in implementing an algorithm, this will be one thing to consider when experimenting with what choice of algorithm they wish to implement, and the architecture they choose to use. For example, if I am using a Shared Memory Machine (SMM), I will tend to avoid implementing an algorithm that requires me to do a lot of global synchronization. This is where one understanding the architecture of a system will become invaluable as this is independent from the computational science and computational complexity theory and more in the realm of implementation, experimentation, and engineering. Some algorithms will naturally not work as well on some architectures over others, as some problems do not mesh well with certain architectures. For example, graph theoretic problems tend to be more difficult to solve when developing parallel algorithms for parallel architectures because there is often a lot more issues relating to how data is partitioned, agglomerated, synchronized, and how processing units communicate. One should not confuse the issues of implementation with the design of algorithms and proving results for algorithms. They usually follow from solving the computational problem as an implementation uses the algorithm to apply it on a system.

To extend on Lambert's point, here is a fine example for his point augmented by what I just explained.

Splendid example (Linear Programming): Simplex method versus Ellipsoid Method. Though it is worth mentioning that Karmarkar's Algorithm improved upon the Ellipsoid method.

Why would this be the case? Most instances (not all) of LP people work with usually aren't the ones that can invoke exponential running times, and most operations done for this algorithm can exploit hardware far better when implemented. It is also worth mentioning that these brute force methods usually are run with time expectations and if not on higher performance machines using anything from branch and bound, to cutting plane methods. The algorithm itself is better in complexity for all instances of LP, but it is a common misconception to think that the brute force method is a superior algorithm if their machine can do it "quicker" when algorithms are formal descriptions, not programs. Simplex has been a hallmark for its superior implementations, not so much for its algorithmic time-complexity (which is still pretty "up in the air" in general). Simplex method is a solid example of an algorithm when implemented in practice can perform well due to the instances most are interested in, though its analysis is a little elusive and time-complexity can be quite poor for worst-case instances.

Notice this this particular example is more about implementation, not the analysis of algorithms themselves at this present time.

Hope this helps!

Daniel, Xiaolong, Ekaterina etc. provided good answers.

-Efficiency is fundamental to algorithms and it is measured with asymptotic notation. I.e. only the limiting behavior is specified. The implication is that we are interested in the behavior of the algorithm (and the corr. implementation) on input with large size. Why? Even the most complex of problems i.e. given two 3D protein structures (one large say A and one small say B) we are interested in determining whether B is an exact substructure of A where we are only interested in the structure and the Amino acids from B need not match that of A, that is, Lucine can take place of Alanine etc.. This can be easily solved if A has 5 Amino acids and B had say 3 or 4. However, if A has 160 AAs and B has 100 AAs the naive methods will not give us an answer in our life time. In fact, for this problem, reasonably “efficient” algorithms do not even exist. Due to variations in processors, compilers, languages, platforms etc. asymptotic notation is a reasonable way of denoting the time consumed by an algorithm.

Pairwise sequence alignment etc. that we take for granted are indeed breakthroughs. Prior to the design of efficient algorithms these were not solvable in a reasonable time. The same goes for many other algorithms. Many of the algorithms/programs that we live with are not exact but approximate algorithms because the exact ones are very expensive. For example, MSA almost always uses approximation because of efficiency reasons (the exact solution is very expensive).

In summary the feasibility of exact/approximate algorithms that we use in bioinformatics (BLAST, Smith Waterman, PROMALS, DALI, ProSMoS etc.) is determined by their (mostly time and sometimes space) efficiency. This is very apt for bio-inf/bio-comp because of the complexity of the problems.

Further, w.r.t. relevance and applicability, the analysis is not always asymptotic. That is, often we try to improve the constant associated with a particular problem. E.g. from 4n we like to get to say cn where c

@Daniel : by 'theoretically better algorithms' I meant algorithms with better time complexity.

E.g. O(n log n) is better than O(n^2)

In practice however, when datasets are not huge, the big O becomes an issue.

Form the basis of conceptualization through the design of the complex algorithms. The principal idea is that the students could analyze a problem, understand it, and try to give an answer to construct a solution (how following a series of steps they can give a solution).

So the importance of exact and effective algorithms (well designed), is the principal category that should be covered at the first time, so we should have a methodology for improving the efficiency of the algorithms. In my classes I use PseInt, which is a very good tool that could be useful for your students too.

we are dealing with space and time complexity; as examples of the latter:

where M is the length of sequence x, N is the length of sequence y: (pair-wise align.)

algorithm of Needleman-Wunsch (1970) is: O(MN)

and Smith-Waterman (1981) is: O(MN)

whereas FASTA average case is: O(MN/20^k)

you can assume that M= 5000 and N=2000;

so, what in case of MSA you can imagine ..!

better algorithm is definitely more useful than better computer

@Lambert But this is ignoring the whole concept of Big-Oh, Big-Omega and Big-Theta and Analysis. We are comparing algorithms in general, not their performance (which relates to implementation) or specific inputs of the algorithm. Depending on the machine, architecture, and implementation performance will vary "in practice". The whole idea is to consider when inputs are large, of course there will be exceptions to the rule if you pick smaller inputs. This is just trivial to see. I mean, as much as people want to poke fun at BubbleSort, it does well when n is small. Why? The number of comparisons is bounded from above by a pretty small number. But, that's not what the sorting problem is. We can't just consider all the easy cases or smaller inputs unless that is prescribed by the problem. I mean, if n