Patterns was conceived and written by Kathryn E. Muratore at the University of California Berkeley under the advisement of Jack F. Kirsch. For any inquiries, comments, or concerns, please contact either Kathryn (kmcelroy@berkeley.edu) or Jack (jfkirsch@berkeley.edu).

What Does Patterns Do?

Patterns takes a sequence alignment and looks for covariation of residues with respect to function. Currently, the program is only capable of comparing groups of sequences assigned one of two functions. Patterns is not a statistical program, but rather serves to automate what a human could do by hand if they had a lot of time and patience. 

The following is an example using a simple case of four closely related peptides, each with 5 residues.

Seq1  MSPFD
Seq2  MAPIV
Seq3  MSVIS
Seq4  MSVIE

Sequences 1 & 2 share a function (A), while sequences 3 & 4 share a different function (B). Since the sequences are short, and there are only 4 of them, you can easily pick out relationships between the peptides. First, residue 1 is completely conserved as Met, and presumably essential for a shared function or structure. Second, residue 3 covaries directly with function; it is Pro for function A and Val for function B. These residues are the most obvious and likely candidates for the difference between the 2 functions. Third, residue 5 appears to be randomly mutating, and therefore does not confer any information about function.

Finally, residues 2 and 4 covary with each other with respect to function. This is an indirect covariation, which may indicate that residue 2 and 4 interact to confer functionality. This indirect covariation can be logically explained as:

	If residue #2 is Ser and residue #4 is Ile, then the function is B.
	Conversely, if residue #2 is Ser and residue #4 is not Ile, then the function is A.
	Additionally, if residue #2 is Ala and residue #4 is Ile, then the function is A.

This indirect covariation is what Patterns can help you find. The covariation does not have to be pair wise for Patterns to find it. In other words, Patterns will be able to find potential covariation between 3, 4 or more residues in certain cases. Finding these higher-order interactions by eye is extremely difficult and time consuming, so this is Patterns' real value.

A note of warning: The reliability of the covariation identified by Patterns is very dependent on the number of sequences that are being analyzed. You have probably noticed in the example above that it is not very convincing that there is covariation at all in these sequences. As a general rule, covariation patterns involving a number of residues that is approaching the number of sequences with a given function should be taken with a grain of salt. 

Patterns will find many more covariation interactions than are reasonable, so the user must use prior knowledge of structure and mutational studies to focus in on the best candidates. For example, it is useful to know if residue 2 and 4 are in direct contact in the structure, or whether previous studies have mutated residue 4 of sequence 3 to a phenylalanine.

How To Use Patterns 

(These instructions are for Windows)

The input for Patterns is a FASTA file of a multiple sequence alignment. The MSA can have gaps (dots, dashes, or tildes). For the example given above, the file would look like:

>Seq1
MSPFD
>Seq2
MAPIV
>Seq3
MSVIS
>Seq4
MSVIE

Patterns allows you to mix up the order of the sequences in the file (i.e., Seq1, then Seq3, then Seq2, then Seq4); the sequences need not be grouped by function in the FASTA file. 

Open the Command Prompt (You may find it in one of the following: Start -> Programs -> Accessories or c:\windows\system32\cmd.exe)

Make a note of where your FASTA and patterns_v4_0.exe files are. In this example, I will have both files in C:\My Sequences\FASTA\, and will change this directory using the cd command:

	C:>cd "My Sequences\FASTA\"

	C:\My Sequences\FASTA>

Now run Patterns:

	C:\My Sequences\FASTA>patterns_v4_0

The program should start running. First it will ask you what type of file to use. For the first run, you want to use your FASTA file. In the future, you can use another file which will be explained later. 

	C:\My Sequences\FASTA>patterns_v2_8

	Would you like to start with a FASTA file?

You want to answer yes to this question, so type "y", “Yes”, or some other variant.

	C:\My Sequences\FASTA>patterns_v4_0

	Would you like to start with a FASTA file?
	y

	What FASTA file would you like to use?

Now just type in exactly the name of your FASTA file.

	What FASTA file would you like to use?
	MySequences.txt

	Do you want to choose a reference sequence for numbering the
	residues?

This is up to you. Some protein families use a particular sequence to standardize the numbering of the residues, or you may be used to looking at a sequence from a particular organism. If you answer yes, all residues will still be analyzed, even if there are gaps in your reference sequence. Once you answer, it will try to find the sequence you want to use.

	Do you want to choose a reference sequence for numbering the
	residues?
	y

	Please give me the first few characters of the reference 
	sequence's name so I can find it.  You can enter up to 10 
	characters to avoid ambiguity.
	se

	Do you want me to use >Seq1 as the reference sequence for 
	numbering?
	n

	Do you want me to use >Seq2 as the reference sequence for 
	numbering?
	y

	What would you like to call the first group of sequences?
	(five characters maximum)

Again, it is up to you how you answer this question. After you assign names, it will ask you which sequences are in each group.

	What would you like to call the first group of sequences?
	(five characters maximum)
	A

	And what is the second group's name?
	B

	Is Seq1 in A? y
	Is Seq2 in A? y	
	Is Seq3 in A? n
	Is Seq4 in A? n

The program is now done asking you questions and will give you information while it is running. The speed of the program is dependent on the number and length of sequences it has to analyze, so be patient! This table shows what you should expect run-times to be on a machine with 256 MB RAM and a Pentium 4 processor:

# sequences	# residues	approximate run-time
17	100	1 second
17	230	5 seconds
9	465	45 seconds
17	465	2 minutes
35	465	20 minutes

When the screen looks like this, the program has been successfully completed, and you will find the output files in the directory that the FASTA file was in (i.e., C:\My Sequences\FASTA).

	There are 2 sequences in A and 2 sequences in B.

	The look-up file was saved as MySequences030112105251.txt
	
	There are 5 residues in the alignment.

	The Patterns file was saved as PatMySequences030112105251.txt.

	Number of residues left to analyze: DONE.

	C:\My Sequences\FASTA>

The numbers at the end of the file names are time-stamps. This prevents files from being overwritten. In the example above, the files were created at 10:52:51 AM on January 12, 2003. Please note that file size is also dependent on the length and number of the sequences. The "Pat" files can be many megabytes.

If you, for some reason, want to re-run Patterns, you can use MySequences030112105251.txt (a "vertically aligned sequence file") instead of your FASTA file by answering “no” to the first question. The most useful reason for doing this is if you want someone else to look at the results, but it is unreasonable to transfer the large "Pat" file.

Patterns Output

The vertically aligned look-up file has 2 parts. The first line is a list of the sequence names, each prefixed by its group number:

1Seq1 1Seq2 2Seq3 2Seq4               

The rest of the file is a transposed alignment.

1 M M M M
2 S A S S
3 P P V V
4 F S I N
5 D V S E

The Pat file has all of the pattern information. First, it lets you know which look-up file was used, what the names of the groups are, which sequences are in which group, and which residues are completely conserved (gaps are ignored for the identification of completely conserved residues):

From MySequences030112105251.txt

First Group  => A:
                Seq1
                Seq2
Second Group => B:
                Seq3
                Seq4

Completely Conserved: 
1 

For each residue which is not conserved, the file will look for a primary pattern. A primary pattern consists of the identity of the amino acids at a given position which are common between both groups of sequences. Again, gaps are ignored during the identification of primary patterns.

PrimaryPattern 2-1: <S-><SS>

The numbers “2-1” tell you that this is the first primary pattern for residue # 2. The letters are the residue (Ser) that is common between the groups. The dash indicates which sequence(s) do(es) not share this residue. The brackets (< >) separate the 2 groups. So “<S->” translates to:

“The first sequence in group A has a serine at position 2, an amino acid which is also present at position 2 in at least one sequence from group B. The second sequence in group 1 does not have a serine at this position.”

Likewise, “<SS>” means:

“Both sequences in group B have serine at position 2, an amino acid which is also present at position 2 in at least one sequence from group A.”

Please note that the order in which amino acids are listed in this file correspond to the list at the top of the file. For example, if Seq3 preceded Seq 2 in the FASTA file, this output file would look identical. However, if Seq2 preceded Seq1 in the FASTA file, then the group A would be listed as follows:

First Group => A:
		   Seq2
		   Seq1

and primary pattern 2-1 would appear as:

PrimaryPattern 2-1: <-S><SS>

Next in the file is a list of all of the non-conserved residues put into one of 5 categories for this primary pattern. For this part, gaps are not ignored.

PrimaryPattern 2-1: <S-><SS>
   conserved in both groups and      conserved in        not conserved
      the same     different           B          A
                        3                         5              
                        4                                        

This tells us 1) no other residues in the alignment have the same primary pattern.
2) Residues 3 and 4 are conserved and different in the 3 sequences for which there is a serine at position 2. Specifically, Seq1 (the only sequence for this pattern in group A) has a “conserved” proline at position 3, while Seq3 and Seq4 (the only sequences for this pattern in group B) have a conserved valine at position 3. The same can be said for position 4, except that a phenylalanine is conserved in group A and an isoleucine is conserved in group B. Notice that we previously identified residue 4 by eye as one which may have indirect covariance with residue 2. Because this is covariance including 2 residues, it appears in this “conserved and different” group.
3) There are no residues in this pattern which are conserved in group B, but the different in group A.
4) Residue 5 is conserved in the pattern sequences for group A, but not for group B. It is “conserved” as an aspartate in group A (Seq1),but not conserved in group B (it is a serine or glutamate).
5) No residues are not conserved in either group of sequences.

Next in the file is a list of subpatterns and the residues which have those subpatterns. Subpatterns are useful for identifying more complex covariance than that between residue 2 and 4. The subpatterns are represented by 1’s and 0’s, meaning, “same” and “different”, respectively. There are (2^n)-1 possible subpatterns. In this case, where there are 2 sequences in group B and 1 sequence in group A, there are 3 possible subpatterns for group B and 1 possible subpattern for group A.

	1:		2:		3:		4:
B: 	<1-><00>	<1-><10>	<1-><01>	<1-><11>(primary)
A:	<0-><11>	<1-><11>(primary)

However, in the case where there is one sequence for a given group, the 1st subpattern for B will be shown instead of the 1st subpattern for A, so there are 0 subpatterns for A and 3 possible for B. .

It seems that matching subpatterns can be found when the sum of the values in the representation is equal for all sequences. Any residue with subpattern 1 may covary with the primary residue since the value for Seq3 equals that for Seq4 (0 = 0). In contrast, a residue from the subpattern 2 covaries with the primary residue only in the context of a residue from group 3 (3-way covariation). This is because Seq3’s value is 1+0, while Seq4’s is 0+1. This trick comes in handy when there are more sequences to pick out higher-ordered covariation.

In this case, there is one residue conserved in group A, but not group B. The subpattern automatically gives all of the sequences for the primary pattern in group A a “1”, because this is the conserved group. Because neither Seq3 or Seq4 have an aspartate as residue 5, those sequences both get 0’s.

Subpattern  2-1-1: <1-><00> 5 

Position 5 may covary with position 2, but it is more likely that position 5 is randomly mutating. Here is the rest of the output:

PrimaryPattern 4-1: <-I><II>
   conserved in both groups and      conserved in        not conserved
      the same     different           B          A
                        2                         5              
                        3                                        

Subpattern  4-1-1: <-1><00> 5 

Notice that residues 3 and 5 do not have primary patterns, because these residues are not shared in common between sequences in different groups. For example, neither Seq3 nor Seq4 have a valine at position 3, and neither Seq1 nor Seq2 have a proline at this position.

This example is very simplified, and does not explore all of the possibilities. Here is part of a real-world example. I know from mutagenesis experiments that residue 39 (using Seq1 for numbering) is important for function. Residue 39 is the second to last residue for this fragment of the alignment.

>Seq1
ap....................PSVFAEVPQAQPVLVFKLIADFREDPDPRKVNLGVGAY
>Seq2
......................--MFENITAAPADPILGLADLFRADERPGKINLGIGVY
>Seq3
mallqsrlllsaprraaataraSSWWSHVEMGPPDPILGVTEAFKRDTNSKKMNLGVGAY
>Seq4
......................MSLFEQLPSFSPDSILGLAQAFQEDPREDKINLLLGTY
>Seq5
m.....................DKLLSSLENIEVDNILKTAREFKEDTCEEKINLSIGVC
>Seq6
......................--MFQKVDAYAGDPILTLMERFKEDPRSDKVNLSIGLY
>Seq7
......................--MLGNLKPQAPDKILALMGEFRADPRQGKIDLGVGVY
>Seq8
ms.......rpfk.........-----DLAPVPLDPVFGLARAAKAAPEP-KADLVIGAY
>Seq9
......................--MFTHLPAPVLDPILSLSVAFRNDPRPQKVDLGIGVY

-----------------------------------------------------------------------

From fasta\char_b.txt

First Group  => A:
                Seq1    
                Seq2   
                Seq3  
                Seq4
                Seq5      
Second Group => B:
                Seq6  
                Seq7  
                Seq8 
                Seq9

Completely Conserved: 
2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   32  35  38  

PrimaryPattern 1-1: <--M-M><--M->
   conserved in both groups and      conserved in        not conserved
      the same     different         B          A
          15            7            2                           
          25           10            2                           
                       17            2                           
                       18            2                           
                       24            2                           
                       27            3                           
                       28            4                           
                       34            5                           

etc.....

PrimaryPattern 39-2: <-V--V><-V-V>
   conserved in both groups and      conserved in        not conserved
      the same     different         B          A
           2           34            1           21            6 
           2                         3           33            7 
           2                         4           37            8 
           2                         5                        10 
           2                         9                        11 
          15                        20                        12 
          17                        25                        13 
          18                        28                        14 
          24                        29                        16 
          27                        36                        19 
                                    40                        22 
                                                              23 
                                                              26 
                                                              30 
                                                              31 

Subpattern   39-2-1: <-1--0><-1-1> 1   3   4   5   20  25  29  36  40  

Subpattern   39-2-2: <-0--1><-1-1> 9   

Subpattern   39-2-3: <-0--0><-1-1> 28  

Subpattern   39-2-4: <-1--1><-0-0> 21  

Subpattern   39-2-5: <-1--1><-1-0> 33  

Subpattern   39-2-6: <-1--1><-0-1> 37  

PrimaryPattern 40-1: <YYYY-><YYYY>

etc....

---------------------------------------------------------------------------------------------------------------------------------

There is possible covariance between residue 39 and 34 (Conserved and Different). Whenever residue 39 is a valine and 34 is an asparagine, the protein has function A, but looking at either residue 34 or 39 independently gives you no information about function.

Another possible higher-order covariance is between residues 39, 33 and 37 (<-1-0> + <-0-1> = <-1-1>). If a protein has isoleucine at both positions 33 and 37 with a valine at position 39, the function is A, but a combination of any two of those 3 residues results in function B. This is illustrated below:

     33  37 39
A
Seq1	V---V-A
Seq2	I---I-V
Seq3	M---V-A
Seq4	I---L-T
Seq5	I---I-V
B
Seq6	V---I-L
Seq7	I---V-V
Seq8	A---I-A
Seq9	V---I-V