src/jalview/datamodel/Alignment.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.8)
   3  * Copyright (C) 2012 J Procter, AM Waterhouse, LM Lui, J Engelhardt, G Barton, M Clamp, S Searle
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
  10  *
  11  * Jalview is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14  * PURPOSE.  See the GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 package jalview.datamodel;
  19
  20 import java.util.*;
  21
  22 /**
  23  * Data structure to hold and manipulate a multiple sequence alignment
  24  */
  25 /**
  26  * @author JimP
  27  *
  28  */
  29 public class Alignment implements AlignmentI
  30 {
  31   protected Alignment dataset;
  32
  33   protected List<SequenceI> sequences;
  34
  35   protected List<SequenceGroup> groups = java.util.Collections
  36           .synchronizedList(new ArrayList<SequenceGroup>());
  37
  38   protected char gapCharacter = '-';
  39
  40   protected int type = NUCLEOTIDE;
  41
  42   public static final int PROTEIN = 0;
  43
  44   public static final int NUCLEOTIDE = 1;
  45
  46   public boolean hasRNAStructure = false;
  47
  48   /** DOCUMENT ME!! */
  49   public AlignmentAnnotation[] annotations;
  50
  51   HiddenSequences hiddenSequences = new HiddenSequences(this);
  52
  53   public Hashtable alignmentProperties;
  54
  55   private void initAlignment(SequenceI[] seqs)
  56   {
  57     int i = 0;
  58
  59     if (jalview.util.Comparison.isNucleotide(seqs))
  60     {
  61       type = NUCLEOTIDE;
  62     }
  63     else
  64     {
  65       type = PROTEIN;
  66     }
  67
  68     sequences = java.util.Collections
  69             .synchronizedList(new ArrayList<SequenceI>());
  70
  71     for (i = 0; i < seqs.length; i++)
  72     {
  73       sequences.add(seqs[i]);
  74     }
  75
  76   }
  77
  78   /**
  79    * Make an alignment from an array of Sequences.
  80    *
  81    * @param sequences
  82    */
  83   public Alignment(SequenceI[] seqs)
  84   {
  85     initAlignment(seqs);
  86   }
  87
  88   /**
  89    * Make a new alignment from an array of SeqCigars
  90    *
  91    * @param seqs
  92    *          SeqCigar[]
  93    */
  94   public Alignment(SeqCigar[] alseqs)
  95   {
  96     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
  97             gapCharacter, new ColumnSelection(), null);
  98     initAlignment(seqs);
  99   }
 100
 101   /**
 102    * Make a new alignment from an CigarArray JBPNote - can only do this when
 103    * compactAlignment does not contain hidden regions. JBPNote - must also check
 104    * that compactAlignment resolves to a set of SeqCigars - or construct them
 105    * appropriately.
 106    *
 107    * @param compactAlignment
 108    *          CigarArray
 109    */
 110   public static AlignmentI createAlignment(CigarArray compactAlignment)
 111   {
 112     throw new Error("Alignment(CigarArray) not yet implemented");
 113     // this(compactAlignment.refCigars);
 114   }
 115
 116   /**
 117    * DOCUMENT ME!
 118    *
 119    * @return DOCUMENT ME!
 120    */
 121   @Override
 122   public List<SequenceI> getSequences()
 123   {
 124     return sequences;
 125   }
 126
 127   @Override
 128   public List<SequenceI> getSequences(
 129           Map<SequenceI, SequenceCollectionI> hiddenReps)
 130   {
 131     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to
 132     // work on this.
 133     return sequences;
 134   }
 135
 136   @Override
 137   public SequenceI[] getSequencesArray()
 138   {
 139     if (sequences == null)
 140       return null;
 141     synchronized (sequences)
 142     {
 143       return sequences.toArray(new SequenceI[sequences.size()]);
 144     }
 145   }
 146
 147   /**
 148    * DOCUMENT ME!
 149    *
 150    * @param i
 151    *          DOCUMENT ME!
 152    *
 153    * @return DOCUMENT ME!
 154    */
 155   @Override
 156   public SequenceI getSequenceAt(int i)
 157   {
 158     synchronized (sequences)
 159     {
 160       if (i > -1 && i < sequences.size())
 161       {
 162         return sequences.get(i);
 163       }
 164     }
 165     return null;
 166   }
 167
 168   /**
 169    * Adds a sequence to the alignment. Recalculates maxLength and size.
 170    *
 171    * @param snew
 172    */
 173   @Override
 174   public void addSequence(SequenceI snew)
 175   {
 176     if (dataset != null)
 177     {
 178       // maintain dataset integrity
 179       if (snew.getDatasetSequence() != null)
 180       {
 181         getDataset().addSequence(snew.getDatasetSequence());
 182       }
 183       else
 184       {
 185         // derive new sequence
 186         SequenceI adding = snew.deriveSequence();
 187         getDataset().addSequence(adding.getDatasetSequence());
 188         snew = adding;
 189       }
 190     }
 191     if (sequences == null)
 192     {
 193       initAlignment(new SequenceI[]
 194       { snew });
 195     }
 196     else
 197     {
 198       synchronized (sequences)
 199       {
 200         sequences.add(snew);
 201       }
 202     }
 203     if (hiddenSequences != null)
 204       hiddenSequences.adjustHeightSequenceAdded();
 205   }
 206
 207   /**
 208    * Adds a sequence to the alignment. Recalculates maxLength and size.
 209    *
 210    * @param snew
 211    */
 212   @Override
 213   public void setSequenceAt(int i, SequenceI snew)
 214   {
 215     SequenceI oldseq = getSequenceAt(i);
 216     deleteSequence(i);
 217     synchronized (sequences)
 218     {
 219       sequences.set(i, snew);
 220     }
 221   }
 222
 223   /**
 224    * DOCUMENT ME!
 225    *
 226    * @return DOCUMENT ME!
 227    */
 228   @Override
 229   public List<SequenceGroup> getGroups()
 230   {
 231     return groups;
 232   }
 233
 234   @Override
 235   public void finalize()
 236   {
 237     if (getDataset() != null)
 238       getDataset().removeAlignmentRef();
 239
 240     dataset = null;
 241     sequences = null;
 242     groups = null;
 243     annotations = null;
 244     hiddenSequences = null;
 245   }
 246
 247   /**
 248    * decrement the alignmentRefs counter by one and call finalize if it goes to
 249    * zero.
 250    */
 251   private void removeAlignmentRef()
 252   {
 253     if (--alignmentRefs == 0)
 254     {
 255       finalize();
 256     }
 257   }
 258
 259   /**
 260    * DOCUMENT ME!
 261    *
 262    * @param s
 263    *          DOCUMENT ME!
 264    */
 265   @Override
 266   public void deleteSequence(SequenceI s)
 267   {
 268     deleteSequence(findIndex(s));
 269   }
 270
 271   /**
 272    * DOCUMENT ME!
 273    *
 274    * @param i
 275    *          DOCUMENT ME!
 276    */
 277   @Override
 278   public void deleteSequence(int i)
 279   {
 280     if (i > -1 && i < getHeight())
 281     {
 282       synchronized (sequences)
 283       {
 284         sequences.remove(i);
 285       }
 286       hiddenSequences.adjustHeightSequenceDeleted(i);
 287     }
 288   }
 289
 290   /*
 291    * (non-Javadoc)
 292    *
 293    * @see jalview.datamodel.AlignmentI#findGroup(jalview.datamodel.SequenceI)
 294    */
 295   @Override
 296   public SequenceGroup findGroup(SequenceI s)
 297   {
 298     synchronized (groups)
 299     {
 300       for (int i = 0; i < this.groups.size(); i++)
 301       {
 302         SequenceGroup sg = groups.get(i);
 303
 304         if (sg.getSequences(null).contains(s))
 305         {
 306           return sg;
 307         }
 308       }
 309     }
 310     return null;
 311   }
 312
 313   /*
 314    * (non-Javadoc)
 315    *
 316    * @see
 317    * jalview.datamodel.AlignmentI#findAllGroups(jalview.datamodel.SequenceI)
 318    */
 319   @Override
 320   public SequenceGroup[] findAllGroups(SequenceI s)
 321   {
 322     ArrayList<SequenceGroup> temp = new ArrayList<SequenceGroup>();
 323
 324     synchronized (groups)
 325     {
 326       int gSize = groups.size();
 327       for (int i = 0; i < gSize; i++)
 328       {
 329         SequenceGroup sg = groups.get(i);
 330         if (sg == null || sg.getSequences(null) == null)
 331         {
 332           this.deleteGroup(sg);
 333           gSize--;
 334           continue;
 335         }
 336
 337         if (sg.getSequences(null).contains(s))
 338         {
 339           temp.add(sg);
 340         }
 341       }
 342     }
 343     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 344     return temp.toArray(ret);
 345   }
 346
 347   /**    */
 348   @Override
 349   public void addGroup(SequenceGroup sg)
 350   {
 351     synchronized (groups)
 352     {
 353       if (!groups.contains(sg))
 354       {
 355         if (hiddenSequences.getSize() > 0)
 356         {
 357           int i, iSize = sg.getSize();
 358           for (i = 0; i < iSize; i++)
 359           {
 360             if (!sequences.contains(sg.getSequenceAt(i)))
 361             {
 362               sg.deleteSequence(sg.getSequenceAt(i), false);
 363               iSize--;
 364               i--;
 365             }
 366           }
 367
 368           if (sg.getSize() < 1)
 369           {
 370             return;
 371           }
 372         }
 373
 374         groups.add(sg);
 375       }
 376     }
 377   }
 378
 379   /**
 380    * remove any annotation that references gp
 381    *
 382    * @param gp
 383    *          (if null, removes all group associated annotation)
 384    */
 385   private void removeAnnotationForGroup(SequenceGroup gp)
 386   {
 387     if (annotations == null || annotations.length == 0)
 388     {
 389       return;
 390     }
 391     // remove annotation very quickly
 392     AlignmentAnnotation[] t, todelete = new AlignmentAnnotation[annotations.length], tokeep = new AlignmentAnnotation[annotations.length];
 393     int i, p, k;
 394     if (gp == null)
 395     {
 396       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 397       {
 398         if (annotations[i].groupRef != null)
 399         {
 400           todelete[p++] = annotations[i];
 401         }
 402         else
 403         {
 404           tokeep[k++] = annotations[i];
 405         }
 406       }
 407     }
 408     else
 409     {
 410       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 411       {
 412         if (annotations[i].groupRef == gp)
 413         {
 414           todelete[p++] = annotations[i];
 415         }
 416         else
 417         {
 418           tokeep[k++] = annotations[i];
 419         }
 420       }
 421     }
 422     if (p > 0)
 423     {
 424       // clear out the group associated annotation.
 425       for (i = 0; i < p; i++)
 426       {
 427         unhookAnnotation(todelete[i]);
 428         todelete[i] = null;
 429       }
 430       t = new AlignmentAnnotation[k];
 431       for (i = 0; i < k; i++)
 432       {
 433         t[i] = tokeep[i];
 434       }
 435       annotations = t;
 436     }
 437   }
 438
 439   @Override
 440   public void deleteAllGroups()
 441   {
 442     synchronized (groups)
 443     {
 444       if (annotations != null)
 445       {
 446         removeAnnotationForGroup(null);
 447       }
 448       groups.clear();
 449     }
 450   }
 451
 452   /**    */
 453   @Override
 454   public void deleteGroup(SequenceGroup g)
 455   {
 456     synchronized (groups)
 457     {
 458       if (groups.contains(g))
 459       {
 460         removeAnnotationForGroup(g);
 461         groups.remove(g);
 462       }
 463     }
 464   }
 465
 466   /**    */
 467   @Override
 468   public SequenceI findName(String name)
 469   {
 470     return findName(name, false);
 471   }
 472
 473   /*
 474    * (non-Javadoc)
 475    *
 476    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 477    */
 478   @Override
 479   public SequenceI findName(String token, boolean b)
 480   {
 481     return findName(null, token, b);
 482   }
 483
 484   /*
 485    * (non-Javadoc)
 486    *
 487    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 488    * boolean)
 489    */
 490   @Override
 491   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 492   {
 493
 494     int i = 0;
 495     SequenceI sq = null;
 496     String sqname = null;
 497     if (startAfter != null)
 498     {
 499       // try to find the sequence in the alignment
 500       boolean matched = false;
 501       while (i < sequences.size())
 502       {
 503         if (getSequenceAt(i++) == startAfter)
 504         {
 505           matched = true;
 506           break;
 507         }
 508       }
 509       if (!matched)
 510       {
 511         i = 0;
 512       }
 513     }
 514     while (i < sequences.size())
 515     {
 516       sq = getSequenceAt(i);
 517       sqname = sq.getName();
 518       if (sqname.equals(token) // exact match
 519               || (b && // allow imperfect matches - case varies
 520               (sqname.equalsIgnoreCase(token))))
 521       {
 522         return getSequenceAt(i);
 523       }
 524
 525       i++;
 526     }
 527
 528     return null;
 529   }
 530
 531   @Override
 532   public SequenceI[] findSequenceMatch(String name)
 533   {
 534     Vector matches = new Vector();
 535     int i = 0;
 536
 537     while (i < sequences.size())
 538     {
 539       if (getSequenceAt(i).getName().equals(name))
 540       {
 541         matches.addElement(getSequenceAt(i));
 542       }
 543       i++;
 544     }
 545
 546     SequenceI[] result = new SequenceI[matches.size()];
 547     for (i = 0; i < result.length; i++)
 548     {
 549       result[i] = (SequenceI) matches.elementAt(i);
 550     }
 551
 552     return result;
 553
 554   }
 555
 556   /*
 557    * (non-Javadoc)
 558    *
 559    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 560    */
 561   @Override
 562   public int findIndex(SequenceI s)
 563   {
 564     int i = 0;
 565
 566     while (i < sequences.size())
 567     {
 568       if (s == getSequenceAt(i))
 569       {
 570         return i;
 571       }
 572
 573       i++;
 574     }
 575
 576     return -1;
 577   }
 578
 579   /*
 580    * (non-Javadoc)
 581    *
 582    * @see
 583    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 584    */
 585   @Override
 586   public int findIndex(SearchResults results)
 587   {
 588     int i = 0;
 589
 590     while (i < sequences.size())
 591     {
 592       if (results.involvesSequence(getSequenceAt(i)))
 593       {
 594         return i;
 595       }
 596       i++;
 597     }
 598     return -1;
 599   }
 600
 601   /**
 602    * DOCUMENT ME!
 603    *
 604    * @return DOCUMENT ME!
 605    */
 606   @Override
 607   public int getHeight()
 608   {
 609     return sequences.size();
 610   }
 611
 612   /**
 613    * DOCUMENT ME!
 614    *
 615    * @return DOCUMENT ME!
 616    */
 617   @Override
 618   public int getWidth()
 619   {
 620     int maxLength = -1;
 621
 622     for (int i = 0; i < sequences.size(); i++)
 623     {
 624       if (getSequenceAt(i).getLength() > maxLength)
 625       {
 626         maxLength = getSequenceAt(i).getLength();
 627       }
 628     }
 629
 630     return maxLength;
 631   }
 632
 633   /**
 634    * DOCUMENT ME!
 635    *
 636    * @param gc
 637    *          DOCUMENT ME!
 638    */
 639   @Override
 640   public void setGapCharacter(char gc)
 641   {
 642     gapCharacter = gc;
 643     synchronized (sequences)
 644     {
 645       for (SequenceI seq : sequences)
 646       {
 647         seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 648                 .replace('-', gc).replace(' ', gc));
 649       }
 650     }
 651   }
 652
 653   /**
 654    * DOCUMENT ME!
 655    *
 656    * @return DOCUMENT ME!
 657    */
 658   @Override
 659   public char getGapCharacter()
 660   {
 661     return gapCharacter;
 662   }
 663
 664   /*
 665    * (non-Javadoc)
 666    *
 667    * @see jalview.datamodel.AlignmentI#isAligned()
 668    */
 669   @Override
 670   public boolean isAligned()
 671   {
 672     return isAligned(false);
 673   }
 674
 675   /*
 676    * (non-Javadoc)
 677    *
 678    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 679    */
 680   @Override
 681   public boolean isAligned(boolean includeHidden)
 682   {
 683     int width = getWidth();
 684     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 685     {
 686       includeHidden = true; // no hidden sequences to check against.
 687     }
 688     for (int i = 0; i < sequences.size(); i++)
 689     {
 690       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 691       {
 692         if (getSequenceAt(i).getLength() != width)
 693         {
 694           return false;
 695         }
 696       }
 697     }
 698
 699     return true;
 700   }
 701
 702   /*
 703    * (non-Javadoc)
 704    *
 705    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 706    * AlignmentAnnotation)
 707    */
 708   @Override
 709   public boolean deleteAnnotation(AlignmentAnnotation aa)
 710   {
 711     return deleteAnnotation(aa, true);
 712   }
 713
 714   @Override
 715   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 716   {
 717     int aSize = 1;
 718
 719     if (annotations != null)
 720     {
 721       aSize = annotations.length;
 722     }
 723
 724     if (aSize < 1)
 725     {
 726       return false;
 727     }
 728
 729     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 730
 731     boolean swap = false;
 732     int tIndex = 0;
 733
 734     for (int i = 0; i < aSize; i++)
 735     {
 736       if (annotations[i] == aa)
 737       {
 738         swap = true;
 739         continue;
 740       }
 741       if (tIndex < temp.length)
 742         temp[tIndex++] = annotations[i];
 743     }
 744
 745     if (swap)
 746     {
 747       annotations = temp;
 748       if (unhook)
 749       {
 750         unhookAnnotation(aa);
 751       }
 752     }
 753     return swap;
 754   }
 755
 756   /**
 757    * remove any object references associated with this annotation
 758    *
 759    * @param aa
 760    */
 761   private void unhookAnnotation(AlignmentAnnotation aa)
 762   {
 763     if (aa.sequenceRef != null)
 764     {
 765       aa.sequenceRef.removeAlignmentAnnotation(aa);
 766     }
 767     if (aa.groupRef != null)
 768     {
 769       // probably need to do more here in the future (post 2.5.0)
 770       aa.groupRef = null;
 771     }
 772   }
 773
 774   /*
 775    * (non-Javadoc)
 776    *
 777    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 778    * AlignmentAnnotation)
 779    */
 780   @Override
 781   public void addAnnotation(AlignmentAnnotation aa)
 782   {
 783     addAnnotation(aa, -1);
 784   }
 785
 786   /*
 787    * (non-Javadoc)
 788    *
 789    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 790    * AlignmentAnnotation, int)
 791    */
 792   @Override
 793   public void addAnnotation(AlignmentAnnotation aa, int pos)
 794   {
 795     if (aa.getRNAStruc() != null)
 796     {
 797       hasRNAStructure = true;
 798     }
 799
 800     int aSize = 1;
 801     if (annotations != null)
 802     {
 803       aSize = annotations.length + 1;
 804     }
 805
 806     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 807     int i = 0;
 808     if (pos == -1 || pos >= aSize)
 809     {
 810       temp[aSize - 1] = aa;
 811     }
 812     else
 813     {
 814       temp[pos] = aa;
 815     }
 816     if (aSize > 1)
 817     {
 818       int p = 0;
 819       for (i = 0; i < (aSize - 1); i++, p++)
 820       {
 821         if (p == pos)
 822         {
 823           p++;
 824         }
 825         if (p < temp.length)
 826         {
 827           temp[p] = annotations[i];
 828         }
 829       }
 830     }
 831
 832     annotations = temp;
 833   }
 834
 835   @Override
 836   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 837   {
 838     if (aa == null || annotations == null || annotations.length - 1 < index)
 839     {
 840       return;
 841     }
 842
 843     int aSize = annotations.length;
 844     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 845
 846     temp[index] = aa;
 847
 848     for (int i = 0; i < aSize; i++)
 849     {
 850       if (i == index)
 851       {
 852         continue;
 853       }
 854
 855       if (i < index)
 856       {
 857         temp[i] = annotations[i];
 858       }
 859       else
 860       {
 861         temp[i] = annotations[i - 1];
 862       }
 863     }
 864
 865     annotations = temp;
 866   }
 867
 868   @Override
 869   /**
 870    * returns all annotation on the alignment
 871    */
 872   public AlignmentAnnotation[] getAlignmentAnnotation()
 873   {
 874     return annotations;
 875   }
 876
 877   @Override
 878   public void setNucleotide(boolean b)
 879   {
 880     if (b)
 881     {
 882       type = NUCLEOTIDE;
 883     }
 884     else
 885     {
 886       type = PROTEIN;
 887     }
 888   }
 889
 890   @Override
 891   public boolean isNucleotide()
 892   {
 893     if (type == NUCLEOTIDE)
 894     {
 895       return true;
 896     }
 897     else
 898     {
 899       return false;
 900     }
 901   }
 902
 903   @Override
 904   public boolean hasRNAStructure()
 905   {
 906     // TODO can it happen that structure is removed from alignment?
 907     return hasRNAStructure;
 908   }
 909
 910   @Override
 911   public void setDataset(Alignment data)
 912   {
 913     if (dataset == null && data == null)
 914     {
 915       // Create a new dataset for this alignment.
 916       // Can only be done once, if dataset is not null
 917       // This will not be performed
 918       SequenceI[] seqs = new SequenceI[getHeight()];
 919       SequenceI currentSeq;
 920       for (int i = 0; i < getHeight(); i++)
 921       {
 922         currentSeq = getSequenceAt(i);
 923         if (currentSeq.getDatasetSequence() != null)
 924         {
 925           seqs[i] = currentSeq.getDatasetSequence();
 926         }
 927         else
 928         {
 929           seqs[i] = currentSeq.createDatasetSequence();
 930         }
 931       }
 932
 933       dataset = new Alignment(seqs);
 934     }
 935     else if (dataset == null && data != null)
 936     {
 937       dataset = data;
 938     }
 939     dataset.addAlignmentRef();
 940   }
 941
 942   /**
 943    * reference count for number of alignments referencing this one.
 944    */
 945   int alignmentRefs = 0;
 946
 947   /**
 948    * increase reference count to this alignment.
 949    */
 950   private void addAlignmentRef()
 951   {
 952     alignmentRefs++;
 953   }
 954
 955   @Override
 956   public Alignment getDataset()
 957   {
 958     return dataset;
 959   }
 960
 961   @Override
 962   public boolean padGaps()
 963   {
 964     boolean modified = false;
 965
 966     // Remove excess gaps from the end of alignment
 967     int maxLength = -1;
 968
 969     SequenceI current;
 970     for (int i = 0; i < sequences.size(); i++)
 971     {
 972       current = getSequenceAt(i);
 973       for (int j = current.getLength(); j > maxLength; j--)
 974       {
 975         if (j > maxLength
 976                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
 977         {
 978           maxLength = j;
 979           break;
 980         }
 981       }
 982     }
 983
 984     maxLength++;
 985
 986     int cLength;
 987     for (int i = 0; i < sequences.size(); i++)
 988     {
 989       current = getSequenceAt(i);
 990       cLength = current.getLength();
 991
 992       if (cLength < maxLength)
 993       {
 994         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
 995         modified = true;
 996       }
 997       else if (current.getLength() > maxLength)
 998       {
 999         current.deleteChars(maxLength, current.getLength());
1000       }
1001     }
1002     return modified;
1003   }
1004
1005   /**
1006    * Justify the sequences to the left or right by deleting and inserting gaps
1007    * before the initial residue or after the terminal residue
1008    *
1009    * @param right
1010    *          true if alignment padded to right, false to justify to left
1011    * @return true if alignment was changed
1012    */
1013   @Override
1014   public boolean justify(boolean right)
1015   {
1016     boolean modified = false;
1017
1018     // Remove excess gaps from the end of alignment
1019     int maxLength = -1;
1020     int ends[] = new int[sequences.size() * 2];
1021     SequenceI current;
1022     for (int i = 0; i < sequences.size(); i++)
1023     {
1024       current = getSequenceAt(i);
1025       // This should really be a sequence method
1026       ends[i * 2] = current.findIndex(current.getStart());
1027       ends[i * 2 + 1] = current.findIndex(current.getStart()
1028               + current.getLength());
1029       boolean hitres = false;
1030       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1031       {
1032         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1033         {
1034           if (!hitres)
1035           {
1036             ends[i * 2] = j;
1037             hitres = true;
1038           }
1039           else
1040           {
1041             ends[i * 2 + 1] = j;
1042             if (j - ends[i * 2] > maxLength)
1043             {
1044               maxLength = j - ends[i * 2];
1045             }
1046           }
1047         }
1048       }
1049     }
1050
1051     maxLength++;
1052     // now edit the flanking gaps to justify to either left or right
1053     int cLength, extent, diff;
1054     for (int i = 0; i < sequences.size(); i++)
1055     {
1056       current = getSequenceAt(i);
1057
1058       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1059       diff = maxLength - cLength; // number of gaps to indent
1060       extent = current.getLength();
1061       if (right)
1062       {
1063         // right justify
1064         if (extent > ends[i * 2 + 1])
1065         {
1066           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1067           modified = true;
1068         }
1069         if (ends[i * 2] > diff)
1070         {
1071           current.deleteChars(0, ends[i * 2] - diff);
1072           modified = true;
1073         }
1074         else
1075         {
1076           if (ends[i * 2] < diff)
1077           {
1078             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1079             modified = true;
1080           }
1081         }
1082       }
1083       else
1084       {
1085         // left justify
1086         if (ends[i * 2] > 0)
1087         {
1088           current.deleteChars(0, ends[i * 2]);
1089           modified = true;
1090           ends[i * 2 + 1] -= ends[i * 2];
1091           extent -= ends[i * 2];
1092         }
1093         if (extent > maxLength)
1094         {
1095           current.deleteChars(maxLength + 1, extent);
1096           modified = true;
1097         }
1098         else
1099         {
1100           if (extent < maxLength)
1101           {
1102             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1103             modified = true;
1104           }
1105         }
1106       }
1107     }
1108     return modified;
1109   }
1110
1111   @Override
1112   public HiddenSequences getHiddenSequences()
1113   {
1114     return hiddenSequences;
1115   }
1116
1117   @Override
1118   public CigarArray getCompactAlignment()
1119   {
1120     synchronized (sequences)
1121     {
1122       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1123       int i = 0;
1124       for (SequenceI seq : sequences)
1125       {
1126         alseqs[i++] = new SeqCigar(seq);
1127       }
1128       CigarArray cal = new CigarArray(alseqs);
1129       cal.addOperation(CigarArray.M, getWidth());
1130       return cal;
1131     }
1132   }
1133
1134   @Override
1135   public void setProperty(Object key, Object value)
1136   {
1137     if (alignmentProperties == null)
1138       alignmentProperties = new Hashtable();
1139
1140     alignmentProperties.put(key, value);
1141   }
1142
1143   @Override
1144   public Object getProperty(Object key)
1145   {
1146     if (alignmentProperties != null)
1147       return alignmentProperties.get(key);
1148     else
1149       return null;
1150   }
1151
1152   @Override
1153   public Hashtable getProperties()
1154   {
1155     return alignmentProperties;
1156   }
1157
1158   AlignedCodonFrame[] codonFrameList = null;
1159
1160   /*
1161    * (non-Javadoc)
1162    *
1163    * @see
1164    * jalview.datamodel.AlignmentI#addCodonFrame(jalview.datamodel.AlignedCodonFrame
1165    * )
1166    */
1167   @Override
1168   public void addCodonFrame(AlignedCodonFrame codons)
1169   {
1170     if (codons == null)
1171       return;
1172     if (codonFrameList == null)
1173     {
1174       codonFrameList = new AlignedCodonFrame[]
1175       { codons };
1176       return;
1177     }
1178     AlignedCodonFrame[] t = new AlignedCodonFrame[codonFrameList.length + 1];
1179     System.arraycopy(codonFrameList, 0, t, 0, codonFrameList.length);
1180     t[codonFrameList.length] = codons;
1181     codonFrameList = t;
1182   }
1183
1184   /*
1185    * (non-Javadoc)
1186    *
1187    * @see jalview.datamodel.AlignmentI#getCodonFrame(int)
1188    */
1189   @Override
1190   public AlignedCodonFrame getCodonFrame(int index)
1191   {
1192     return codonFrameList[index];
1193   }
1194
1195   /*
1196    * (non-Javadoc)
1197    *
1198    * @see
1199    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1200    */
1201   @Override
1202   public AlignedCodonFrame[] getCodonFrame(SequenceI seq)
1203   {
1204     if (seq == null || codonFrameList == null)
1205       return null;
1206     Vector cframes = new Vector();
1207     for (int f = 0; f < codonFrameList.length; f++)
1208     {
1209       if (codonFrameList[f].involvesSequence(seq))
1210         cframes.addElement(codonFrameList[f]);
1211     }
1212     if (cframes.size() == 0)
1213       return null;
1214     AlignedCodonFrame[] cfr = new AlignedCodonFrame[cframes.size()];
1215     cframes.copyInto(cfr);
1216     return cfr;
1217   }
1218
1219   /*
1220    * (non-Javadoc)
1221    *
1222    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1223    */
1224   @Override
1225   public AlignedCodonFrame[] getCodonFrames()
1226   {
1227     return codonFrameList;
1228   }
1229
1230   /*
1231    * (non-Javadoc)
1232    *
1233    * @seejalview.datamodel.AlignmentI#removeCodonFrame(jalview.datamodel.
1234    * AlignedCodonFrame)
1235    */
1236   @Override
1237   public boolean removeCodonFrame(AlignedCodonFrame codons)
1238   {
1239     if (codons == null || codonFrameList == null)
1240       return false;
1241     boolean removed = false;
1242     int i = 0, iSize = codonFrameList.length;
1243     while (i < iSize)
1244     {
1245       if (codonFrameList[i] == codons)
1246       {
1247         removed = true;
1248         if (i + 1 < iSize)
1249         {
1250           System.arraycopy(codonFrameList, i + 1, codonFrameList, i, iSize
1251                   - i - 1);
1252         }
1253         iSize--;
1254       }
1255       else
1256       {
1257         i++;
1258       }
1259     }
1260     return removed;
1261   }
1262
1263   @Override
1264   public void append(AlignmentI toappend)
1265   {
1266     if (toappend == this)
1267     {
1268       System.err.println("Self append may cause a deadlock.");
1269     }
1270     // TODO test this method for a future 2.5 release
1271     // currently tested for use in jalview.gui.SequenceFetcher
1272     boolean samegap = toappend.getGapCharacter() == getGapCharacter();
1273     char oldc = toappend.getGapCharacter();
1274     boolean hashidden = toappend.getHiddenSequences() != null
1275             && toappend.getHiddenSequences().hiddenSequences != null;
1276     // get all sequences including any hidden ones
1277     List<SequenceI> sqs = (hashidden) ? toappend.getHiddenSequences()
1278             .getFullAlignment().getSequences() : toappend.getSequences();
1279     if (sqs != null)
1280     {
1281       synchronized (sqs)
1282       {
1283         for (SequenceI addedsq : sqs)
1284         {
1285           if (!samegap)
1286           {
1287             char[] oldseq = addedsq.getSequence();
1288             for (int c = 0; c < oldseq.length; c++)
1289             {
1290               if (oldseq[c] == oldc)
1291               {
1292                 oldseq[c] = gapCharacter;
1293               }
1294             }
1295           }
1296           addSequence(addedsq);
1297         }
1298       }
1299     }
1300     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1301     for (int a = 0; alan != null && a < alan.length; a++)
1302     {
1303       addAnnotation(alan[a]);
1304     }
1305     AlignedCodonFrame[] acod = toappend.getCodonFrames();
1306     for (int a = 0; acod != null && a < acod.length; a++)
1307     {
1308       this.addCodonFrame(acod[a]);
1309     }
1310     List<SequenceGroup> sg = toappend.getGroups();
1311     if (sg != null)
1312     {
1313       for (SequenceGroup _sg : sg)
1314       {
1315         addGroup(_sg);
1316       }
1317     }
1318     if (toappend.getHiddenSequences() != null)
1319     {
1320       HiddenSequences hs = toappend.getHiddenSequences();
1321       if (hiddenSequences == null)
1322       {
1323         hiddenSequences = new HiddenSequences(this);
1324       }
1325       if (hs.hiddenSequences != null)
1326       {
1327         for (int s = 0; s < hs.hiddenSequences.length; s++)
1328         {
1329           // hide the newly appended sequence in the alignment
1330           if (hs.hiddenSequences[s] != null)
1331           {
1332             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1333           }
1334         }
1335       }
1336     }
1337     if (toappend.getProperties() != null)
1338     {
1339       // we really can't do very much here - just try to concatenate strings
1340       // where property collisions occur.
1341       Enumeration key = toappend.getProperties().keys();
1342       while (key.hasMoreElements())
1343       {
1344         Object k = key.nextElement();
1345         Object ourval = this.getProperty(k);
1346         Object toapprop = toappend.getProperty(k);
1347         if (ourval != null)
1348         {
1349           if (ourval.getClass().equals(toapprop.getClass())
1350                   && !ourval.equals(toapprop))
1351           {
1352             if (ourval instanceof String)
1353             {
1354               // append strings
1355               this.setProperty(k, ((String) ourval) + "; "
1356                       + ((String) toapprop));
1357             }
1358             else
1359             {
1360               if (ourval instanceof Vector)
1361               {
1362                 // append vectors
1363                 Enumeration theirv = ((Vector) toapprop).elements();
1364                 while (theirv.hasMoreElements())
1365                 {
1366                   ((Vector) ourval).addElement(theirv);
1367                 }
1368               }
1369             }
1370           }
1371         }
1372         else
1373         {
1374           // just add new property directly
1375           setProperty(k, toapprop);
1376         }
1377
1378       }
1379     }
1380   }
1381
1382   @Override
1383   public AlignmentAnnotation findOrCreateAnnotation(String name,
1384           String calcId, boolean autoCalc, SequenceI seqRef,
1385           SequenceGroup groupRef)
1386   {
1387     assert (name != null);
1388     if (annotations != null)
1389     {
1390       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1391       {
1392         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1393                 && (calcId == null || annot.getCalcId().equals(calcId))
1394                 && annot.sequenceRef == seqRef
1395                 && annot.groupRef == groupRef)
1396         {
1397           return annot;
1398         }
1399       }
1400     }
1401     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1402             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1403     annot.hasText = false;
1404     annot.setCalcId(new String(calcId));
1405     annot.autoCalculated = autoCalc;
1406     if (seqRef != null)
1407     {
1408       annot.setSequenceRef(seqRef);
1409     }
1410     annot.groupRef = groupRef;
1411     addAnnotation(annot);
1412
1413     return annot;
1414   }
1415
1416   @Override
1417   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1418   {
1419     ArrayList<AlignmentAnnotation> aa = new ArrayList<AlignmentAnnotation>();
1420     for (AlignmentAnnotation a : getAlignmentAnnotation())
1421     {
1422       if (a.getCalcId() == calcId
1423               || (a.getCalcId() != null && calcId != null && a.getCalcId()
1424                       .equals(calcId)))
1425       {
1426         aa.add(a);
1427       }
1428     }
1429     return aa;
1430   }
1431
1432   @Override
1433   public void moveSelectedSequencesByOne(SequenceGroup sg,
1434           Map<SequenceI, SequenceCollectionI> map, boolean up)
1435   {
1436     synchronized (sequences)
1437     {
1438       if (up)
1439       {
1440
1441         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1442         {
1443           SequenceI seq = sequences.get(i);
1444           if (!sg.getSequences(map).contains(seq))
1445           {
1446             continue;
1447           }
1448
1449           SequenceI temp = sequences.get(i - 1);
1450           if (sg.getSequences(null).contains(temp))
1451           {
1452             continue;
1453           }
1454
1455           sequences.set(i, temp);
1456           sequences.set(i - 1, seq);
1457         }
1458       }
1459       else
1460       {
1461         for (int i = sequences.size() - 2; i > -1; i--)
1462         {
1463           SequenceI seq = sequences.get(i);
1464           if (!sg.getSequences(map).contains(seq))
1465           {
1466             continue;
1467           }
1468
1469           SequenceI temp = sequences.get(i + 1);
1470           if (sg.getSequences(map).contains(temp))
1471           {
1472             continue;
1473           }
1474
1475           sequences.set(i, temp);
1476           sequences.set(i + 1, seq);
1477         }
1478       }
1479
1480     }
1481   }
1482  @Override
1483  public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1484  {
1485    alignmentAnnotation.validateRangeAndDisplay();
1486    if (isNucleotide() && alignmentAnnotation.isValidStruc())
1487    {
1488      hasRNAStructure = true;
1489    }
1490  }
1491  @Override
1492 public int getEndRes()
1493 {
1494   return getWidth()-1;
1495 }@Override
1496 public int getStartRes()
1497 {
1498   return 0;
1499 }
1500 }