MUSCA: Multiple Sequence Alignment

What Is This Tool For? - Input - Options - Parameters - Mode of Operation - Output - References

What Is This Tool For?

This tool allows the user to align multiple streams of letters so as to reveal salient features that are potentially present in a given collection of event streams.

We define the multiple sequence alignment problem as follows: given a collection of N sequences, insert spaces (gaps) into the sequences or at the beginning/end of them so that the resulting sequences all have the same length. One can typically use a scoring function, that rewards agreements and penalizes mismatches and gaps, in order to quantitatively determine the quality of the resulting alignment. Traditionally, multiple sequence alignment was used as a first step in the path of discovering patterns that are shared among sequences (proteins, dna, etc.). In the early 90's, researchers began exploring the use of pattern discovery as a means to determine and report multiple sequence alignments.

__________________________________________________________________________

__________________________________________________________________________

Input Format

The input to be processed consists of streams of symbols. Each of the streams is to be preceded by a label line. Thus, an input set comprising N data streams should consist of 2*N input lines (N 'label' lines and N 'data' lines).

In the case of amino acid sequences the input can be given in FASTA format: it will be processed automatically and turned into the well-formed input with alternating 'label' lines and 'data' lines. Obviously, 'data' lines can all have different lengths.

For amino acid-based inputs, the amino acids in the final alignment can be colored-coded based on their hydropathy -- this is optional and controlled by selecting the appropriate box in the main page of the multiple sequence alignment tool.

NOTE: All the symbols in the input will be turned into lower case before processing, unless you have selected the 'upper case' option: then, case will be preserved and a symbol in lower case will be considered different from its upper case version.

__________________________________________________________________________

__________________________________________________________________________

Options

The following options are available to the user:

• Discovery Using Equivalences: this allows you to select between equivalence-based pattern discovery over exact pattern discovery. If you select to run equivalence-based pattern discovery you will also have to provide the sets of symbols which you consider equivalent and which could be replacing one another.
• Exact Discovery: this allows you to run exact pattern discovery where there is provision for equivalent input symbols. This may be desirable for some applications.
• Seq Version: this allows you to select between the two instances of the pattern discovery problem:
  if selected: the algorithm will discover those patterns that appear in at least K sequences of the input
  if not selected: the algorithm will discover those patterns that appear at least K times in the input (all of which could be in one sequence!!).
• Remove Overlaps: this allows you to make the algorithm reject every pattern P with at least two instances that are overlapping one another. For example, the pattern A..A.CA..A appears twice in ADEAKCAMLARCAVIA and both of its instances are overlapping -- setting the binary variable will force the algorithm to ignore such patterns. This is particularly useful for handling sequences with regions that have low complexities such trains of G's or A's. Note: if set, the results will NOT be complete. This option is meant for quick-and-dirty checks.
• Upper Case: this allows you to force Teiresias to only consider input symbols that are in upper case when carrying out pattern discovery: the remaining patterns will then be passed on to MUSCA for processing and the generation of the multiple sequence alignment. One example use of this variable is in masking pathological regions (e.g. poly-A, poly-S, regions of low-complexity etc) by (a) turning the symbols of the region in question into lower case and (b) setting the variable. Teiresias will then skip over these regions and your output will only contain patterns involving the rest of the input. It is assumed of course that the rest of your input is in upper case.
• Hydropathy Coloring: this allows you to optionally color the amino acids that participate in aligned blocks, using a hydropathy-related color.
• Only amino acid characters: this will identify and report any characters in the data part of the input that are not among the 20 amino acid symbols.
• Only nucleic acid characters: this will identify and report any characters in the data part of the input that are not among the 4 nucleic acid symbols.
• Accept all characters: turns off the checks for permitted characters.

__________________________________________________________________________

Parameters

The parameters you can set here are the following:

• Max Brackets: it controls the maximum number of brackets that one can have in a given pattern.
• L: this is the minimum number of literals (i.e. non-wild-card characters) in your pattern.
• W: this is the maximum extent spanned by any L consecutive literals in the reported patterns. For a choice of the values L and W, the patterns that we report are guaranteed to have the following properties:

  a) they span at least L positions.

  b) if you look at any consecutive L literals (note: consecutive does NOT mean contiguous!) in a reported pattern the first and last literal are not more than W positions apart.

  c) if a pattern is reported as appearing 10 times in the input, we guarantee that it cannot be made more specific through appending/prepending another string or through dereferencing a wild-card character without either decreasing the number of its occurrences or violating the L/W constraint.

• K (resp. Q): this is the desired minimum (resp. maximum) support for a pattern that can have one of the following two meanings:

  if SEQ_VERSION is set you are solving the problem: "find all patterns that are supported by at least K (and not more than Q) streams"

  if SEQ_VERSION is not set you are solving the problem: "find all patterns that are supported by at least K (and not more than Q) instances."

  Note that the output in this case is typically much bigger than in the previous version of the problem. The default value of Q is 2147483647.

• Equivalence Sets: You can run the Teiresias pattern discovery algorithms in one of two modes:
• exact pattern discovery, and
• equivalence-based pattern discovery.

In the latter case, you need to specify what symbols of the allowed alphabet can be treated as equivalent during the actual pattern discovery process. You define equivalence sets by listing each set on a separate line. Each line corresponds to a single set and should contain the symbols without any spaces belonging to the set. The equivalency sets can overlap (e.g. KR and KRH appearing on two different lines). Also, if a symbol is in a class by itself, you should NOT list it in this window.

NOTE 1: in our extensive work on the analysis of protein sequences, we have discovered that use of scoring matrices is limiting since it may result in restrictive choices: allowing you to define equivalency sets permits to bypass such restrictions and provide for more flexibility during the discovery process.

NOTE 2: If you work with proteins the following equivalence sets may prove useful:

• if you wish to favor amino acid substitutions that preserve the chemical character of the amino acid you can use the following equivalences:

  AG, DE, FY, KR, ILMV, QN, ST

• if you wish to favor amino acid substitutions that preserve the structural character of the amino acid you can use the following equivalences:

  CS, DLN, EQ, FHWY, ITV, KMR

• if you wish to favor the amino acid substitutions that are dictated by a Blosum-50 substitution matrix you can use the following equivalences (but be prepared to be flooded by a much higher number of discovered patterns):

• if your domain of interest is outside computational biology then you must generate a set of equivalences by taking into account domain specific information.

Rules of Thumb for Setting the Parameters

Typical starting choices for K (= support) should be in the interval [N/2, N]. Regarding the choices for L and W our recommendation is to start with values that correspond to 'high-degree' of 'local' conservation and progressively relax the constraints. Here is a typical choice 'schedule' for an input of N=20 sequences: L=6 W=8 K=10, L=6 W=9 K=10, L=6 W=10 K=10, L=6 W=12 K=10, L=5 W=12 K=10, L=5 W=12 K=9, L=5 W=12 K=8, L=5 W=12 K=7, L=5 W=12 K=6, etc. As you try these combinations of values you typically expect to see the results improve and converge toward a stable, "best" alignment -- given the performance of the algorithm you will actually be able to very quickly try these combinations before deciding on the combination that is best.

__________________________________________________________________________

__________________________________________________________________________

Mode Of Operation

MUSCA is a two-phase algorithm for computing the multiple sequence alignment of a set of N sequences. During the first phase, we use Teiresias to discover motifs that are common among a subset of the N sequences. These motifs are used in the second phase to generate and report the multiple sequence alignment. In particular, the motifs are first mapped to vertices of a directed graph: if two motifs p_i and p_j do not occur simultaneously in any sequence then there is no edge connecting the corresponding vertices of the graph; the vertices corresponding to p_i and p_j will be connected by an edge with direction from p_i to p_j if p_i occurs before p_j in all the sequences where they both appear; the labels of the edges depend on three things: whether p_i and p_j are pair-wise incompatible, have overlapping instances, or are pair-wise compatible but do not overlap. Those vertices that are joined by incompatible edges or participate in inconsistent cycles form the basic non-feasible sets. After labeling the vertices of the reduced graph with the help of a simple cost function, we use a greedy algorithm to obtain a solution to a weighted set-cover problem that essentially identifies the minimum number of motifs/vertices to be removed. The resulting graph is used to determine blocks that involve overlapping feasible motifs. We obtain the final alignment by properly aligning the blocks and padding up the existing gaps.

The conceptual underpinnings of this method can be traced to earlier work where the multiple alignment is driven by pair-wise comparisons of the processed input sequences. What distinguishes our work is that it is independent of the order in which the input sequences are given and that its starting point is a K-wise alignment (with K being user-defined and generally larger than 2). Two situations where the algorithm excels are: a) inputs where the various sequences share domains that are present in some of the sequences only, and b) inputs that comprise two or more subsets with high conservation within each set but low conservation across the subsets.

The resulting algorithm works very efficiently with large inputs that contain long sequences and a detailed description of it together with results on several benchmark datasets can be found in the references.

__________________________________________________________________________

__________________________________________________________________________

Output Format

After you prepared and entered the input in the provided window, click on the COMPUTE button. Once the processing has completed, the results will be reported as follows:

__________________________________________________________________________

__________________________________________________________________________

References

• Parida, L., A. Floratos and I. Rigoutsos, "An Approximation Algorithm for Alignment of Multiple Sequences Using Motif Discovery." Journal Of Combinatorial Optimization. 3(2/3): 247-275, July 1999.
• Parida, L., A. Floratos, and I. Rigoutsos, "MUSCA: An Algorithm for Constrained Alignment of Multiple Data Sequences." In Proceedings Ninth Workshop on Genome Informatics, Tokyo, Japan. 1998.