src/jalview/datamodel/Alignment.java

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