src/jalview/datamodel/Alignment.java

   1 /*\r
   2  * Jalview - A Sequence Alignment Editor and Viewer\r
   3  * Copyright (C) 2005 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle\r
   4  *\r
   5  * This program is free software; you can redistribute it and/or\r
   6  * modify it under the terms of the GNU General Public License\r
   7  * as published by the Free Software Foundation; either version 2\r
   8  * of the License, or (at your option) any later version.\r
   9  *\r
  10  * This program is distributed in the hope that it will be useful,\r
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13  * GNU General Public License for more details.\r
  14  *\r
  15  * You should have received a copy of the GNU General Public License\r
  16  * along with this program; if not, write to the Free Software\r
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA\r
  18  */\r
  19 package jalview.datamodel;\r
  20 \r
  21 import jalview.analysis.*;\r
  22 \r
  23 import jalview.util.*;\r
  24 \r
  25 import java.util.*;\r
  26 \r
  27 /** Data structure to hold and manipulate a multiple sequence alignment\r
  28  */\r
  29 public class Alignment implements AlignmentI\r
  30 {\r
  31     protected Alignment dataset;\r
  32     protected Vector sequences;\r
  33     protected Vector groups = new Vector();\r
  34     protected char gapCharacter = '-';\r
  35     protected int type = NUCLEOTIDE;\r
  36     public static final int PROTEIN = 0;\r
  37     public static final int NUCLEOTIDE = 1;\r
  38 \r
  39     /** DOCUMENT ME!! */\r
  40     public AlignmentAnnotation[] annotations;\r
  41 \r
  42     HiddenSequences hiddenSequences = new HiddenSequences(this);\r
  43 \r
  44 \r
  45     /** Make an alignment from an array of Sequences.\r
  46      *\r
  47      * @param sequences\r
  48      */\r
  49     public Alignment(SequenceI[] seqs)\r
  50     {\r
  51         int i=0;\r
  52 \r
  53         if( jalview.util.Comparison.isNucleotide(seqs))\r
  54           type = NUCLEOTIDE;\r
  55         else\r
  56           type = PROTEIN;\r
  57 \r
  58         sequences = new Vector();\r
  59 \r
  60         for (i = 0; i < seqs.length; i++)\r
  61         {\r
  62             sequences.addElement(seqs[i]);\r
  63         }\r
  64     }\r
  65 \r
  66     /**\r
  67      * DOCUMENT ME!\r
  68      *\r
  69      * @return DOCUMENT ME!\r
  70      */\r
  71     public Vector getSequences()\r
  72     {\r
  73         return sequences;\r
  74     }\r
  75 \r
  76     /**\r
  77      * DOCUMENT ME!\r
  78      *\r
  79      * @param i DOCUMENT ME!\r
  80      *\r
  81      * @return DOCUMENT ME!\r
  82      */\r
  83     public SequenceI getSequenceAt(int i)\r
  84     {\r
  85         if (i < sequences.size())\r
  86         {\r
  87             return (SequenceI) sequences.elementAt(i);\r
  88         }\r
  89 \r
  90         return null;\r
  91     }\r
  92 \r
  93     /** Adds a sequence to the alignment.  Recalculates maxLength and size.\r
  94      *\r
  95      * @param snew\r
  96      */\r
  97     public void addSequence(SequenceI snew)\r
  98     {\r
  99         sequences.addElement(snew);\r
 100     }\r
 101 \r
 102     /**\r
 103      * DOCUMENT ME!\r
 104      *\r
 105      * @param seq DOCUMENT ME!\r
 106      */\r
 107     public void addSequence(SequenceI[] seq)\r
 108     {\r
 109         for (int i = 0; i < seq.length; i++)\r
 110         {\r
 111             addSequence(seq[i]);\r
 112         }\r
 113     }\r
 114 \r
 115     /** Adds a sequence to the alignment.  Recalculates maxLength and size.\r
 116      *\r
 117      * @param snew\r
 118      */\r
 119     public void setSequenceAt(int i, SequenceI snew)\r
 120     {\r
 121         SequenceI oldseq = getSequenceAt(i);\r
 122         deleteSequence(oldseq);\r
 123 \r
 124         sequences.setElementAt(snew, i);\r
 125     }\r
 126 \r
 127     /**\r
 128      * DOCUMENT ME!\r
 129      *\r
 130      * @return DOCUMENT ME!\r
 131      */\r
 132     public Vector getGroups()\r
 133     {\r
 134         return groups;\r
 135     }\r
 136 \r
 137     /** Takes out columns consisting entirely of gaps (-,.," ")\r
 138      */\r
 139     public void removeGaps()\r
 140     {\r
 141         SequenceI current;\r
 142         int iSize = getWidth();\r
 143 \r
 144         for (int i = 0; i < iSize; i++)\r
 145         {\r
 146             boolean delete = true;\r
 147 \r
 148             for (int j = 0; j < getHeight(); j++)\r
 149             {\r
 150                 current = getSequenceAt(j);\r
 151 \r
 152                 if (current.getLength() > i)\r
 153                 {\r
 154                     /* MC Should move this to a method somewhere */\r
 155                     if (!jalview.util.Comparison.isGap(current.getCharAt(i)))\r
 156                     {\r
 157                         delete = false;\r
 158                     }\r
 159                 }\r
 160             }\r
 161 \r
 162             if (delete)\r
 163             {\r
 164                 deleteColumns(i, i);\r
 165                 iSize--;\r
 166                 i--;\r
 167             }\r
 168         }\r
 169     }\r
 170 \r
 171     /** Removes a range of columns (start to end inclusive).\r
 172      *\r
 173      * @param start Start column in the alignment\r
 174      * @param end End column in the alignment\r
 175      */\r
 176     public void deleteColumns(int start, int end)\r
 177     {\r
 178         deleteColumns(0, getHeight() - 1, start, end);\r
 179     }\r
 180 \r
 181     /**\r
 182      * DOCUMENT ME!\r
 183      *\r
 184      * @param seq1 DOCUMENT ME!\r
 185      * @param seq2 DOCUMENT ME!\r
 186      * @param start DOCUMENT ME!\r
 187      * @param end DOCUMENT ME!\r
 188      */\r
 189     public void deleteColumns(int seq1, int seq2, int start, int end)\r
 190     {\r
 191         for (int i = 0; i <= (end - start); i++)\r
 192         {\r
 193             for (int j = seq1; j <= seq2; j++)\r
 194             {\r
 195                 getSequenceAt(j).deleteCharAt(start);\r
 196             }\r
 197         }\r
 198     }\r
 199 \r
 200     /**\r
 201      * DOCUMENT ME!\r
 202      *\r
 203      * @param i DOCUMENT ME!\r
 204      */\r
 205     public void trimLeft(int i)\r
 206     {\r
 207         int j, jSize = getHeight();\r
 208         for (j = 0; j < jSize; j++)\r
 209         {\r
 210             SequenceI s = getSequenceAt(j);\r
 211             int newstart = s.findPosition(i);\r
 212 \r
 213             if(i>s.getLength())\r
 214             {\r
 215               sequences.removeElement(s);\r
 216               j--;\r
 217               jSize--;\r
 218             }\r
 219             else\r
 220             {\r
 221               s.setStart(newstart);\r
 222               s.setSequence(s.getSequence().substring(i));\r
 223             }\r
 224         }\r
 225     }\r
 226 \r
 227     /**\r
 228      * DOCUMENT ME!\r
 229      *\r
 230      * @param i DOCUMENT ME!\r
 231      */\r
 232     public void trimRight(int i)\r
 233     {\r
 234         for (int j = 0; j < getHeight(); j++)\r
 235         {\r
 236             SequenceI s = getSequenceAt(j);\r
 237             int newend = s.findPosition(i);\r
 238 \r
 239             s.setEnd(newend);\r
 240             if(s.getLength()>i)\r
 241               s.setSequence(s.getSequence().substring(0, i + 1));\r
 242         }\r
 243     }\r
 244 \r
 245     /**\r
 246      * DOCUMENT ME!\r
 247      *\r
 248      * @param s DOCUMENT ME!\r
 249      */\r
 250     public void deleteSequence(SequenceI s)\r
 251     {\r
 252         for (int i = 0; i < getHeight(); i++)\r
 253         {\r
 254             if (getSequenceAt(i) == s)\r
 255             {\r
 256                 deleteSequence(i);\r
 257             }\r
 258         }\r
 259     }\r
 260 \r
 261     /**\r
 262      * DOCUMENT ME!\r
 263      *\r
 264      * @param i DOCUMENT ME!\r
 265      */\r
 266     public void deleteSequence(int i)\r
 267     {\r
 268         sequences.removeElementAt(i);\r
 269     }\r
 270 \r
 271     /**\r
 272      * DOCUMENT ME!\r
 273      *\r
 274      * @param threshold DOCUMENT ME!\r
 275      * @param sel DOCUMENT ME!\r
 276      *\r
 277      * @return DOCUMENT ME!\r
 278      */\r
 279     public Vector removeRedundancy(float threshold, Vector sel)\r
 280     {\r
 281         Vector del = new Vector();\r
 282 \r
 283         for (int i = 1; i < sel.size(); i++)\r
 284         {\r
 285             for (int j = 0; j < i; j++)\r
 286             {\r
 287                 // Only do the comparison if either have not been deleted\r
 288                 if (!del.contains((SequenceI) sel.elementAt(i)) ||\r
 289                         !del.contains((SequenceI) sel.elementAt(j)))\r
 290                 {\r
 291                     // use PID instead of Comparison (which is really not pleasant)\r
 292                     float pid = Comparison.PID((SequenceI) sel.elementAt(j),\r
 293                             (SequenceI) sel.elementAt(i));\r
 294 \r
 295                     if (pid >= threshold)\r
 296                     {\r
 297                         // Delete the shortest one\r
 298                         if (((SequenceI) sel.elementAt(j)).getSequence().length() > ((SequenceI) sel\r
 299                                                                                          .elementAt(\r
 300                                     i)).getSequence().length())\r
 301                         {\r
 302                             del.addElement(sel.elementAt(i));\r
 303                         }\r
 304                         else\r
 305                         {\r
 306                             del.addElement(sel.elementAt(i));\r
 307                         }\r
 308                     }\r
 309                 }\r
 310             }\r
 311         }\r
 312 \r
 313         // Now delete the sequences\r
 314         for (int i = 0; i < del.size(); i++)\r
 315         {\r
 316             deleteSequence((SequenceI) del.elementAt(i));\r
 317         }\r
 318 \r
 319         return del;\r
 320     }\r
 321 \r
 322     /**    */\r
 323     public SequenceGroup findGroup(int i)\r
 324     {\r
 325         return findGroup(getSequenceAt(i));\r
 326     }\r
 327 \r
 328     /**    */\r
 329     public SequenceGroup findGroup(SequenceI s)\r
 330     {\r
 331         for (int i = 0; i < this.groups.size(); i++)\r
 332         {\r
 333             SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
 334 \r
 335             if (sg.sequences.contains(s))\r
 336             {\r
 337                 return sg;\r
 338             }\r
 339         }\r
 340 \r
 341         return null;\r
 342     }\r
 343 \r
 344     /**\r
 345      * DOCUMENT ME!\r
 346      *\r
 347      * @param s DOCUMENT ME!\r
 348      *\r
 349      * @return DOCUMENT ME!\r
 350      */\r
 351     public SequenceGroup[] findAllGroups(SequenceI s)\r
 352     {\r
 353         Vector temp = new Vector();\r
 354 \r
 355         int gSize = groups.size();\r
 356         for (int i = 0; i < gSize; i++)\r
 357         {\r
 358             SequenceGroup sg = (SequenceGroup) groups.elementAt(i);\r
 359             if(sg==null || sg.sequences==null)\r
 360             {\r
 361               this.deleteGroup(sg);\r
 362               gSize--;\r
 363               continue;\r
 364             }\r
 365 \r
 366             if (sg.sequences.contains(s))\r
 367             {\r
 368                 temp.addElement(sg);\r
 369             }\r
 370         }\r
 371 \r
 372         SequenceGroup[] ret = new SequenceGroup[temp.size()];\r
 373 \r
 374         for (int i = 0; i < temp.size(); i++)\r
 375         {\r
 376             ret[i] = (SequenceGroup) temp.elementAt(i);\r
 377         }\r
 378 \r
 379         return ret;\r
 380     }\r
 381 \r
 382 \r
 383 \r
 384     /**    */\r
 385     public void addGroup(SequenceGroup sg)\r
 386     {\r
 387         if (!groups.contains(sg))\r
 388         {\r
 389             groups.addElement(sg);\r
 390         }\r
 391     }\r
 392 \r
 393     /**\r
 394      * DOCUMENT ME!\r
 395      */\r
 396     public void deleteAllGroups()\r
 397     {\r
 398         groups.removeAllElements();\r
 399 \r
 400         int i = 0;\r
 401 \r
 402         while (i < sequences.size())\r
 403         {\r
 404             SequenceI s = getSequenceAt(i);\r
 405             s.setColor(java.awt.Color.white);\r
 406             i++;\r
 407         }\r
 408     }\r
 409 \r
 410     /**    */\r
 411     public void deleteGroup(SequenceGroup g)\r
 412     {\r
 413         if (groups.contains(g))\r
 414         {\r
 415             groups.removeElement(g);\r
 416         }\r
 417     }\r
 418 \r
 419     /**    */\r
 420     public SequenceI findName(String name)\r
 421     {\r
 422         int i = 0;\r
 423 \r
 424         while (i < sequences.size())\r
 425         {\r
 426             if (getSequenceAt(i).getName().equals(name))\r
 427             {\r
 428                 return getSequenceAt(i);\r
 429             }\r
 430 \r
 431             i++;\r
 432         }\r
 433 \r
 434         return null;\r
 435     }\r
 436 \r
 437 \r
 438     /**    */\r
 439     public int findIndex(SequenceI s)\r
 440     {\r
 441         int i = 0;\r
 442 \r
 443         while (i < sequences.size())\r
 444         {\r
 445             if (s == getSequenceAt(i))\r
 446             {\r
 447                 return i;\r
 448             }\r
 449 \r
 450             i++;\r
 451         }\r
 452 \r
 453         return -1;\r
 454     }\r
 455 \r
 456     /**\r
 457      * DOCUMENT ME!\r
 458      *\r
 459      * @return DOCUMENT ME!\r
 460      */\r
 461     public int getHeight()\r
 462     {\r
 463         return sequences.size();\r
 464     }\r
 465 \r
 466     /**\r
 467      * DOCUMENT ME!\r
 468      *\r
 469      * @return DOCUMENT ME!\r
 470      */\r
 471     public int getWidth()\r
 472     {\r
 473         int maxLength = -1;\r
 474 \r
 475         for (int i = 0; i < sequences.size(); i++)\r
 476         {\r
 477             if (getSequenceAt(i).getLength() > maxLength)\r
 478             {\r
 479                 maxLength = getSequenceAt(i).getLength();\r
 480             }\r
 481         }\r
 482 \r
 483         return maxLength;\r
 484     }\r
 485 \r
 486     /**\r
 487      * DOCUMENT ME!\r
 488      *\r
 489      * @return DOCUMENT ME!\r
 490      */\r
 491     public int getMaxIdLength()\r
 492     {\r
 493         int max = 0;\r
 494         int i = 0;\r
 495 \r
 496         while (i < sequences.size())\r
 497         {\r
 498             SequenceI seq = getSequenceAt(i);\r
 499             String tmp = seq.getName() + "/" + seq.getStart() + "-" +\r
 500                 seq.getEnd();\r
 501 \r
 502             if (tmp.length() > max)\r
 503             {\r
 504                 max = tmp.length();\r
 505             }\r
 506 \r
 507             i++;\r
 508         }\r
 509 \r
 510         return max;\r
 511     }\r
 512 \r
 513     /**\r
 514      * DOCUMENT ME!\r
 515      *\r
 516      * @param gc DOCUMENT ME!\r
 517      */\r
 518     public void setGapCharacter(char gc)\r
 519     {\r
 520         gapCharacter = gc;\r
 521 \r
 522         for (int i = 0; i < sequences.size(); i++)\r
 523         {\r
 524             Sequence seq = (Sequence) sequences.elementAt(i);\r
 525             seq.sequence = seq.sequence.replace('.', gc);\r
 526             seq.sequence = seq.sequence.replace('-', gc);\r
 527             seq.sequence = seq.sequence.replace(' ', gc);\r
 528         }\r
 529     }\r
 530 \r
 531     /**\r
 532      * DOCUMENT ME!\r
 533      *\r
 534      * @return DOCUMENT ME!\r
 535      */\r
 536     public char getGapCharacter()\r
 537     {\r
 538         return gapCharacter;\r
 539     }\r
 540 \r
 541     /**\r
 542      * DOCUMENT ME!\r
 543      *\r
 544      * @return DOCUMENT ME!\r
 545      */\r
 546     public Vector getAAFrequency()\r
 547     {\r
 548         return AAFrequency.calculate(sequences, 0, getWidth());\r
 549     }\r
 550 \r
 551     /**\r
 552      * DOCUMENT ME!\r
 553      *\r
 554      * @return DOCUMENT ME!\r
 555      */\r
 556     public boolean isAligned()\r
 557     {\r
 558         int width = getWidth();\r
 559 \r
 560         for (int i = 0; i < sequences.size(); i++)\r
 561         {\r
 562             if (getSequenceAt(i).getLength() != width)\r
 563             {\r
 564                 return false;\r
 565             }\r
 566         }\r
 567 \r
 568         return true;\r
 569     }\r
 570 \r
 571     /**\r
 572      * DOCUMENT ME!\r
 573      *\r
 574      * @param aa DOCUMENT ME!\r
 575      */\r
 576     public void deleteAnnotation(AlignmentAnnotation aa)\r
 577     {\r
 578         int aSize = 1;\r
 579 \r
 580         if (annotations != null)\r
 581         {\r
 582             aSize = annotations.length;\r
 583         }\r
 584 \r
 585         AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];\r
 586 \r
 587         int tIndex = 0;\r
 588 \r
 589         for (int i = 0; i < aSize; i++)\r
 590         {\r
 591             if (annotations[i] == aa)\r
 592             {\r
 593                 continue;\r
 594             }\r
 595 \r
 596             temp[tIndex] = annotations[i];\r
 597             tIndex++;\r
 598         }\r
 599 \r
 600         annotations = temp;\r
 601     }\r
 602 \r
 603 \r
 604     public void adjustSequenceAnnotations()\r
 605     {\r
 606       if(annotations!=null)\r
 607       {\r
 608         for (int a = 0; a < annotations.length; a++)\r
 609         {\r
 610           if (annotations[a].sequenceRef != null)\r
 611           {\r
 612             annotations[a].adjustForAlignment();\r
 613           }\r
 614         }\r
 615       }\r
 616     }\r
 617 \r
 618     /**\r
 619      * DOCUMENT ME!\r
 620      *\r
 621      * @param aa DOCUMENT ME!\r
 622      */\r
 623     public void addAnnotation(AlignmentAnnotation aa)\r
 624     {\r
 625         int aSize = 1;\r
 626         if (annotations != null)\r
 627         {\r
 628             aSize = annotations.length + 1;\r
 629         }\r
 630 \r
 631         AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];\r
 632 \r
 633         temp[aSize-1] = aa;\r
 634 \r
 635         int i = 0;\r
 636 \r
 637         if (aSize > 1)\r
 638         {\r
 639             for (i = 0; i < (aSize-1); i++)\r
 640             {\r
 641                 temp[i] = annotations[i];\r
 642             }\r
 643         }\r
 644 \r
 645         annotations = temp;\r
 646     }\r
 647 \r
 648     public void setAnnotationIndex(AlignmentAnnotation aa, int index)\r
 649     {\r
 650       if(aa==null || annotations==null || annotations.length-1<index)\r
 651         return;\r
 652 \r
 653       int aSize = annotations.length;\r
 654       AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];\r
 655 \r
 656       temp[index] = aa;\r
 657 \r
 658       for (int i = 0; i < aSize; i++)\r
 659       {\r
 660         if(i==index)\r
 661           continue;\r
 662 \r
 663         if(i<index)\r
 664           temp[i] = annotations[i];\r
 665         else\r
 666           temp[i] = annotations[i-1];\r
 667       }\r
 668 \r
 669         annotations = temp;\r
 670     }\r
 671 \r
 672     /**\r
 673      * DOCUMENT ME!\r
 674      *\r
 675      * @return DOCUMENT ME!\r
 676      */\r
 677     public AlignmentAnnotation[] getAlignmentAnnotation()\r
 678     {\r
 679         return annotations;\r
 680     }\r
 681 \r
 682     public void setNucleotide(boolean b)\r
 683     {\r
 684       if(b)\r
 685         type = NUCLEOTIDE;\r
 686       else\r
 687         type = PROTEIN;\r
 688     }\r
 689 \r
 690     public boolean isNucleotide()\r
 691     {\r
 692       if(type==NUCLEOTIDE)\r
 693         return true;\r
 694       else\r
 695         return false;\r
 696     }\r
 697 \r
 698     public void setDataset(Alignment data)\r
 699     {\r
 700       if(dataset==null && data==null)\r
 701       {\r
 702         // Create a new dataset for this alignment.\r
 703         // Can only be done once, if dataset is not null\r
 704         // This will not be performed\r
 705         Sequence[] seqs = new Sequence[getHeight()];\r
 706         for (int i = 0; i < getHeight(); i++)\r
 707         {\r
 708 \r
 709           seqs[i] = new Sequence(getSequenceAt(i).getName(),\r
 710                                  AlignSeq.extractGaps(\r
 711                                      jalview.util.Comparison.GapChars,\r
 712                                      getSequenceAt(i).getSequence()\r
 713                                  ),\r
 714                                  getSequenceAt(i).getStart(),\r
 715                                  getSequenceAt(i).getEnd());\r
 716 \r
 717           getSequenceAt(i).setDatasetSequence(seqs[i]);\r
 718         }\r
 719 \r
 720         dataset = new Alignment(seqs);\r
 721       }\r
 722       else if(dataset==null && data!=null)\r
 723       {\r
 724         dataset = data;\r
 725       }\r
 726     }\r
 727 \r
 728     public Alignment getDataset()\r
 729     {\r
 730       return dataset;\r
 731     }\r
 732 \r
 733     public boolean padGaps() {\r
 734       boolean modified=false;\r
 735 \r
 736       //Remove excess gaps from the end of alignment\r
 737       int maxLength = -1;\r
 738 \r
 739       SequenceI current;\r
 740       for (int i = 0; i < sequences.size(); i++)\r
 741       {\r
 742         current = getSequenceAt(i);\r
 743         for (int j = current.getLength(); j > maxLength; j--)\r
 744         {\r
 745           if (j > maxLength && !jalview.util.Comparison.isGap(\r
 746               current.getCharAt(j)))\r
 747           {\r
 748             maxLength = j;\r
 749             break;\r
 750           }\r
 751         }\r
 752       }\r
 753 \r
 754       maxLength++;\r
 755 \r
 756       for (int i = 0; i < sequences.size();\r
 757            i++)\r
 758       {\r
 759         current = getSequenceAt(i);\r
 760 \r
 761         if (current.getLength() < maxLength)\r
 762         {\r
 763           current.insertCharAt(maxLength - 1, gapCharacter);\r
 764           modified=true;\r
 765         }\r
 766         else if(current.getLength() > maxLength)\r
 767         {\r
 768           current.deleteChars(maxLength, current.getLength());\r
 769         }\r
 770       }\r
 771       return modified;\r
 772     }\r
 773 \r
 774     public HiddenSequences getHiddenSequences()\r
 775     {\r
 776       return hiddenSequences;\r
 777     }\r
 778 \r
 779 }\r