Multiple sequence alignment system and method

Abstract

The method of the present invention aligns a set of N sequences, where N is large. The alignment brings out the best commonality of the N sequences. The method is performed in two stages. A first stage involving discovering motifs, and a second stage involve motif pruning and sequence alignment. The present invention also provides an additional constraint, K, as a user defined control parameter. The additional parameter constrains the alignment of the N sequences to have at least K of the N sequences agree on a character, whenever possible, in the alignment. The alignment number, K, provides a natural constraint for dealing with a large number of sequences in that a commonality across most, if not all sequences is required to be detected.

What is claimed is:  
     
       1. A method for aligning characters in character sequences, said method steps comprising: 
       identifying a plurality of motifs from the character sequences based on sub-sequences in the character sequence;  
       removing a subset of motifs from said plurality of identified motifs which prevent alignment of the character sequences; and  
       aligning the character sequences based on the remaining motifs.  
     
     
       2. The method according to claim  1 , further comprising receiving as input from a user an alignment number, K, constraining the sequence alignment to have at least K of N character sequences agree on a character in said character sequence alignment. 
     
     
       3. The method according to claim  1 , wherein the step of identifying said plurality of motifs from the character sequences comprises identifying repeated character patterns that appear in at least two of said character sequences. 
     
     
       4. The method according to claim  1 , wherein said plurality of motifs identified from said character sequences are irredundant motifs. 
     
     
       5. The method according to claim  1 , wherein the step of removing a subset of motifs comprise those motifs whose removal maximizes the number of sequence characters in columns in the sequence alignment in which at least K seuquence characters are identical. 
     
     
       6. The method according to claim  5 , wherein a weighted set covering algorithm is performed to maximize the number of sequence characters in each column in the sequence alignment in which at least K sequence characters are identical. 
     
     
       7. The method according to claim  1 , wherein the step of removing a subset of motifs comprise those motifs whose removal maximizes the number of characters in each column in the sequence alignment in which at least K characters are identical. 
     
     
       8. The method according to claim  6 , wherein a weighted set covering algorithm is performed to maximize the number of columns in the sequence alignment in which at least K characters are identical. 
     
     
       9. The method according to claim  1 , wherein the step of removing a subset of motifs from said plurality of identified motifs further comprises identifying offending motifs by constructing a directed graph comprising a plurality of vertices and directed edges between said plurality of vertices, wherein each of said plurality of vertices corresponds to one of said plurality of motifs. 
     
     
       10. The method according to claim  9 , wherein a first vertex in said directed graph will be connected to a second vertex when the motifs corresponding to the respective first and second vertexes occur simultaneously in at least one of said plurality of input sequences. 
     
     
       11. The method according to claim  9 , wherein the step of removing a subset of motifs further comprises identifying offending motifs which violate one or more infeasibility tests from said directed graph. 
     
     
       12. The method according to claim  11 , wherein said one or more infeasibility tests include a pairwise incompatibility test, a smallest cycles test, and a closed paths with inconsistencies test. 
     
     
       13. The method according to claim  12 , wherein said smallest cycles test comprises a depth first search on said directed graph. 
     
     
       14. The method according to claim  12 , wherein said closed paths with inconsistencies test comprises a breadth first search on said directed graph. 
     
     
       15. The method according to claim  12 , wherein said pairwise incompatibility test further comprises a domain crossing mismatch test and an overlap mismatch test. 
     
     
       16. The method according to claim  15 , wherein said domain crossing mismatch test further comprises identifying a pair of motifs comprising a first motif and a second motif, where the position of said first motif is to the left of said second motif in a first character sequence from said character sequences, and where the position of said first motif is to the right of said second motif in a second character sequence from said character sequences. 
     
     
       17. The method according to claim  16 , wherein said overlap mismatch test further comprises 
       identifying a first motif and a second motif in a first sequence and a second sequence; and  
       determining whether all possible alignments of said first motif in said first and second sequences precludes the simultaneous alignment of said second motif in said first and second sequences.  
     
     
       18. The method according to claim  1 , wherein the step of aligning the character sequences is performed simultaneously. 
     
     
       19. A method for aligning characters in character sequences, said method steps comprising: 
       identifying a plurality of motifs from said character sequences;  
       identifying offending motifs from said plurality of motifs, wherein said offending motifs prevent sequence alignment of the character sequences;  
       removing at least one offending motif from consideration at a sequence alignment stage to maximize a pre-specified cost function, wherein the remaining motifs define a feasible set of motifs; and  
       aligning said character sequences from said feasible set of motifs.  
     
     
       20. The method according to claim  19 , further comprising receiving as input from a user an alignment number, K, constraining the sequence alignment to have at least K of N character sequences agree on a character in said character sequence alignment. 
     
     
       21. The method according to claim  19 , wherein the step of identifying motifs from the character sequences comprises identifying repeated character patterns that appear in at least two character sequences. 
     
     
       22. The method according to claim  19 , wherein the pre-specified cost function maximizes the number of sequence characters in columns in the sequence alignment in which at least K sequence characters are identical, wherein K defines an alignment number with some predefined value greater than or equal to 2. 
     
     
       23. The method according to claim  19 , wherein the step of identifying offending motifs from said plurality of motifs further comprises constructing a directed graph comprising a plurality of vertices and directed edges between said plurality of vertices, each of said vertices corresponding to one of said plurality of identified motifs. 
     
     
       24. The method according to claim  19 , wherein the step of removing a subset of motifs further comprises identifying offending motifs which violate one or more infeasibility tests from said directed graph. 
     
     
       25. The method according to claim  24 , where said one or more infeasibility tests comprise a forbidden pairs test, a smallest cycles test, and a closed paths with inconsistencies test. 
     
     
       26. The method according to claim  25 , wherein said forbidden pairs test further comprises a domain crossing mismatch test and an overlap mismatch test. 
     
     
       27. The method according to claim  25 , wherein said smallest cycles test comprises a depth first search on said directed graph. 
     
     
       28. The method according to claim  25 , wherein said closed paths with inconsistencies test comprises a breadth first search on said directed graph. 
     
     
       29. The method according to claim  26 , wherein said domain crossing mismatch test further comprises identifying a pair of motifs comprising a first motif and a second motif, where the position of said first motif is to the left of said second motif in a first character sequence from said character sequences, and where the position of said first motif is to the right of said second motif in a second character sequence from said character sequences. 
     
     
       30. The method according to claim  26 , wherein said overlap mismatch test further comprises 
       identifying a first motif and a second motif in a first sequence and a second sequence; and  
       determining whether all possible alignments of said first motif in said first and second sequences precludes the simultaneous alignment of said second motif in said first and second sequences.  
     
     
       31. A computer program device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for aligning characters in character sequences, said method steps comprising: 
       identifying a plurality of motifs;  
       identifying offending motifs from said plurality of motifs, wherein said offending motifs prevent sequence alignment of the character sequences;  
       removing at least one offending motif from consideration at a sequence alignment stage, wherein those motifs not removed from said plurality of motifs define a feasible set of motifs; and  
       aligning said character sequences from said feasible set of motifs to maximize a pre-specified cost function.  
     
     
       32. The method according to claim  31 , further comprising receiving as input from a user an alignment number, K, constraining the sequence alignment to have at least K of N character sequences agree on a character in said character sequence alignment. 
     
     
       33. The method according to claim  31 , wherein the step of removing said at least one attending motif from said plurality of identified motifs further comprises identifying offending motifs by constructing a directed graph comprising a plurality of vertices and directed edges between said plurality of vertices, wherein each of said plurality of vertices corresponds to one of said plurality of motifs. 
     
     
       34. The method according to claim  33 , wherein a first vertex in said directed graph will be connected to a second vertex when the motifs corresponding to the respective first and second vertexes occur simultaneously in at least one of said plurality of input sequences. 
     
     
       35. The method according to claim  33 , wherein the step of removing said at least one offending motif further comprises identifying offending motifs which violate one or more infeasibility tests from said directed graph. 
     
     
       36. The method according to claim  35 , wherein said one or more infeasibility tests include a pairwise incompatibility test, a smallest cycles test, and a closed paths with inconsistencies test. 
     
     
       37. The method according to claim  35 , wherein said smallest cycles test comprises a depth first search on said directed graph. 
     
     
       38. The method according to claim  35 , wherein said closed paths with inconsistencies test comprises a breadth first search on said directed graph. 
     
     
       39. The method according to claim  35 , wherein said pairwise incompatibility test further comprises a domain crossing mismatch test and an overlap mismatch test.