Version 2003-03-18: Release of Mar 18 2003

• Speed-up of chaining phase
  Previously, m multiMEMs occuring in k > 2 sequences were chained in time $O(k\cdot m^2)$, i.e., the running time of the algorithm was quadratic in the number m of multiMEMs. This can be a serious drawback if m is large. To overcome this obstacle, we implemented a variant of an algorithm devised by Zhang et al. [ZRHM94]. This algorithm takes advantage of the geometric nature of the problem. It is based on kd-trees, a data structure known from computational geometry [Ben90]. As is typical with kd-tree methods, no rigorous analysis of the running time of the algorithm is known. However, our experiments show that it gives a considerable speed-up in practice.

• Using arbitrary alignment tools
  Previously, only ClustalW could be used to close short gaps between multiMEMs occuring in k > 2 sequences. Furthermore, its parameters were fixed. Now, virtually any multiple (or pairwise) alignment tool and parameter setting can be used with the help of wrapper scripts which are passed to option -msascript.

• Same chaining output between Linux and Solaris
  Previously, the output of the chaining phase could differ depending on the operating system. This could happen when there was a choice between several equally long subchains. Furthermore, this could lead to a different overall number of chained multiMEMs--especially when the resulting gaps were aligned recursively. Consequently the alignment could differ substantially. Now the chaining phase will always get the same results independant of the operating system. Using the same parameter settings for mga will aways result in the same chain and alignment. Note that because of the changes the alignment produced by mga may differ from that of earlier versions. Furthermore, chains may differ depending on the (not recommended) use of option -nofast for three or more sequences.

• Sequence limit displayed
  The command line output now shows the maximum number of sequences mga can handle.

• Changes to options
  new: options -msascript, -alignedseqs and -width
  modified: options -xml and -nofast
  consistent: options -clustalw and -greedy cannot be combined
  no limit: options -gl and -maxdist can receive values higher than 5,000