src/jalview/datamodel/Alignment.java

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