src/jalview/datamodel/Alignment.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ 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.datamodel.AlignedCodonFrame.SequenceToSequenceMapping;
  25 import jalview.io.FastaFile;
  26 import jalview.util.Comparison;
  27 import jalview.util.LinkedIdentityHashSet;
  28 import jalview.util.MessageManager;
  29
  30 import java.util.ArrayList;
  31 import java.util.Arrays;
  32 import java.util.BitSet;
  33 import java.util.Collections;
  34 import java.util.Enumeration;
  35 import java.util.HashSet;
  36 import java.util.Hashtable;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.Map;
  40 import java.util.Set;
  41 import java.util.Vector;
  42
  43 /**
  44  * Data structure to hold and manipulate a multiple sequence alignment
  45  */
  46 /**
  47  * @author JimP
  48  *
  49  */
  50 public class Alignment implements AlignmentI
  51 {
  52   private Alignment dataset;
  53
  54   private List<SequenceI> sequences;
  55
  56   protected List<SequenceGroup> groups;
  57
  58   protected char gapCharacter = '-';
  59
  60   private boolean nucleotide = true;
  61
  62   public boolean hasRNAStructure = false;
  63
  64   public AlignmentAnnotation[] annotations;
  65
  66   HiddenSequences hiddenSequences;
  67
  68   HiddenColumns hiddenCols;
  69
  70   public Hashtable alignmentProperties;
  71
  72   private List<AlignedCodonFrame> codonFrameList;
  73
  74   private void initAlignment(SequenceI[] seqs)
  75   {
  76     groups = Collections.synchronizedList(new ArrayList<SequenceGroup>());
  77     hiddenSequences = new HiddenSequences(this);
  78     hiddenCols = new HiddenColumns();
  79     codonFrameList = new ArrayList<>();
  80
  81     nucleotide = Comparison.isNucleotide(seqs);
  82
  83     sequences = Collections.synchronizedList(new ArrayList<SequenceI>());
  84
  85     for (int 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
 104     initAlignment(seqs);
 105
 106     /*
 107      * Share the same dataset sequence mappings (if any).
 108      */
 109     if (dataset == null && al.getDataset() == null)
 110     {
 111       this.setCodonFrames(al.getCodonFrames());
 112     }
 113   }
 114
 115   /**
 116    * Make an alignment from an array of Sequences.
 117    *
 118    * @param sequences
 119    */
 120   public Alignment(SequenceI[] seqs)
 121   {
 122     initAlignment(seqs);
 123   }
 124
 125   /**
 126    * Make a new alignment from an array of SeqCigars
 127    *
 128    * @param seqs
 129    *          SeqCigar[]
 130    */
 131   public Alignment(SeqCigar[] alseqs)
 132   {
 133     SequenceI[] seqs = SeqCigar.createAlignmentSequences(alseqs,
 134             gapCharacter, new HiddenColumns(), null);
 135     initAlignment(seqs);
 136   }
 137
 138   /**
 139    * Make a new alignment from an CigarArray JBPNote - can only do this when
 140    * compactAlignment does not contain hidden regions. JBPNote - must also check
 141    * that compactAlignment resolves to a set of SeqCigars - or construct them
 142    * appropriately.
 143    *
 144    * @param compactAlignment
 145    *          CigarArray
 146    */
 147   public static AlignmentI createAlignment(CigarArray compactAlignment)
 148   {
 149     throw new Error(MessageManager
 150             .getString("error.alignment_cigararray_not_implemented"));
 151     // this(compactAlignment.refCigars);
 152   }
 153
 154   @Override
 155   public List<SequenceI> getSequences()
 156   {
 157     return sequences;
 158   }
 159
 160   @Override
 161   public List<SequenceI> getSequences(
 162           Map<SequenceI, SequenceCollectionI> hiddenReps)
 163   {
 164     // TODO: in jalview 2.8 we don't do anything with hiddenreps - fix design to
 165     // work on this.
 166     return sequences;
 167   }
 168
 169   @Override
 170   public SequenceI[] getSequencesArray()
 171   {
 172     if (sequences == null)
 173     {
 174       return null;
 175     }
 176     synchronized (sequences)
 177     {
 178       return sequences.toArray(new SequenceI[sequences.size()]);
 179     }
 180   }
 181
 182   /**
 183    * Returns a map of lists of sequences keyed by sequence name.
 184    *
 185    * @return
 186    */
 187   @Override
 188   public Map<String, List<SequenceI>> getSequencesByName()
 189   {
 190     return AlignmentUtils.getSequencesByName(this);
 191   }
 192
 193   @Override
 194   public SequenceI getSequenceAt(int i)
 195   {
 196     synchronized (sequences)
 197     {
 198
 199       if (i > -1 && i < sequences.size())
 200       {
 201         return sequences.get(i);
 202       }
 203     }
 204
 205     return null;
 206   }
 207
 208   @Override
 209   public SequenceI getSequenceAtAbsoluteIndex(int i)
 210   {
 211     SequenceI seq = null;
 212     if (getHiddenSequences().getSize() > 0)
 213     {
 214       seq = getHiddenSequences().getHiddenSequence(i);
 215       if (seq == null)
 216       {
 217         // didn't find the sequence in the hidden sequences, get it from the
 218         // alignment
 219         int index = getHiddenSequences().findIndexWithoutHiddenSeqs(i);
 220         seq = getSequenceAt(index);
 221       }
 222     }
 223     else
 224     {
 225       seq = getSequenceAt(i);
 226     }
 227     return seq;
 228   }
 229
 230   /**
 231    * Adds a sequence to the alignment. Recalculates maxLength and size. Note
 232    * this currently does not recalculate whether or not the alignment is
 233    * nucleotide, so mixed alignments may have undefined behaviour.
 234    *
 235    * @param snew
 236    */
 237   @Override
 238   public void addSequence(SequenceI snew)
 239   {
 240     if (dataset != null)
 241     {
 242
 243       // maintain dataset integrity
 244       SequenceI dsseq = snew.getDatasetSequence();
 245       if (dsseq == null)
 246       {
 247         // derive new sequence
 248         SequenceI adding = snew.deriveSequence();
 249         snew = adding;
 250         dsseq = snew.getDatasetSequence();
 251       }
 252       if (getDataset().findIndex(dsseq) == -1)
 253       {
 254         getDataset().addSequence(dsseq);
 255       }
 256
 257     }
 258     if (sequences == null)
 259     {
 260       initAlignment(new SequenceI[] { snew });
 261     }
 262     else
 263     {
 264       synchronized (sequences)
 265       {
 266         sequences.add(snew);
 267       }
 268     }
 269     if (hiddenSequences != null)
 270     {
 271       hiddenSequences.adjustHeightSequenceAdded();
 272     }
 273   }
 274
 275   @Override
 276   public SequenceI replaceSequenceAt(int i, SequenceI snew)
 277   {
 278     synchronized (sequences)
 279     {
 280       if (sequences.size() > i)
 281       {
 282         return sequences.set(i, snew);
 283
 284       }
 285       else
 286       {
 287         sequences.add(snew);
 288         hiddenSequences.adjustHeightSequenceAdded();
 289       }
 290       return null;
 291     }
 292   }
 293
 294   /**
 295    * DOCUMENT ME!
 296    *
 297    * @return DOCUMENT ME!
 298    */
 299   @Override
 300   public List<SequenceGroup> getGroups()
 301   {
 302     return groups;
 303   }
 304
 305   @Override
 306   public void finalize() throws Throwable
 307   {
 308     if (getDataset() != null)
 309     {
 310       getDataset().removeAlignmentRef();
 311     }
 312
 313     nullReferences();
 314     super.finalize();
 315   }
 316
 317   /**
 318    * Defensively nulls out references in case this object is not garbage
 319    * collected
 320    */
 321   void nullReferences()
 322   {
 323     dataset = null;
 324     sequences = null;
 325     groups = null;
 326     annotations = null;
 327     hiddenSequences = null;
 328   }
 329
 330   /**
 331    * decrement the alignmentRefs counter by one and null references if it goes
 332    * to zero.
 333    *
 334    * @throws Throwable
 335    */
 336   private void removeAlignmentRef() throws Throwable
 337   {
 338     if (--alignmentRefs == 0)
 339     {
 340       nullReferences();
 341     }
 342   }
 343
 344   @Override
 345   public void deleteSequence(SequenceI s)
 346   {
 347     synchronized (sequences)
 348     {
 349       deleteSequence(findIndex(s));
 350     }
 351   }
 352
 353   @Override
 354   public void deleteSequence(int i)
 355   {
 356     synchronized (sequences)
 357     {
 358       if (i > -1 && i < getHeight())
 359       {
 360         sequences.remove(i);
 361         hiddenSequences.adjustHeightSequenceDeleted(i);
 362       }
 363     }
 364   }
 365
 366   @Override
 367   public void deleteHiddenSequence(int i)
 368   {
 369     synchronized (sequences)
 370     {
 371       if (i > -1 && i < getHeight())
 372       {
 373         sequences.remove(i);
 374       }
 375     }
 376   }
 377
 378   /*
 379    * (non-Javadoc)
 380    *
 381    * @see jalview.datamodel.AlignmentI#findGroup(jalview.datamodel.SequenceI)
 382    */
 383   @Override
 384   public SequenceGroup findGroup(SequenceI seq, int position)
 385   {
 386     synchronized (groups)
 387     {
 388       for (SequenceGroup sg : groups)
 389       {
 390         if (sg.getSequences(null).contains(seq))
 391         {
 392           if (position >= sg.getStartRes() && position <= sg.getEndRes())
 393           {
 394             return sg;
 395           }
 396         }
 397       }
 398     }
 399     return null;
 400   }
 401
 402   /*
 403    * (non-Javadoc)
 404    *
 405    * @see
 406    * jalview.datamodel.AlignmentI#findAllGroups(jalview.datamodel.SequenceI)
 407    */
 408   @Override
 409   public SequenceGroup[] findAllGroups(SequenceI s)
 410   {
 411     ArrayList<SequenceGroup> temp = new ArrayList<>();
 412
 413     synchronized (groups)
 414     {
 415       int gSize = groups.size();
 416       for (int i = 0; i < gSize; i++)
 417       {
 418         SequenceGroup sg = groups.get(i);
 419         if (sg == null || sg.getSequences() == null)
 420         {
 421           this.deleteGroup(sg);
 422           gSize--;
 423           continue;
 424         }
 425
 426         if (sg.getSequences().contains(s))
 427         {
 428           temp.add(sg);
 429         }
 430       }
 431     }
 432     SequenceGroup[] ret = new SequenceGroup[temp.size()];
 433     return temp.toArray(ret);
 434   }
 435
 436   /**    */
 437   @Override
 438   public void addGroup(SequenceGroup sg)
 439   {
 440     synchronized (groups)
 441     {
 442       if (!groups.contains(sg))
 443       {
 444         if (hiddenSequences.getSize() > 0)
 445         {
 446           int i, iSize = sg.getSize();
 447           for (i = 0; i < iSize; i++)
 448           {
 449             if (!sequences.contains(sg.getSequenceAt(i)))
 450             {
 451               sg.deleteSequence(sg.getSequenceAt(i), false);
 452               iSize--;
 453               i--;
 454             }
 455           }
 456
 457           if (sg.getSize() < 1)
 458           {
 459             return;
 460           }
 461         }
 462         sg.setContext(this, true);
 463         groups.add(sg);
 464       }
 465     }
 466   }
 467
 468   /**
 469    * remove any annotation that references gp
 470    *
 471    * @param gp
 472    *          (if null, removes all group associated annotation)
 473    */
 474   private void removeAnnotationForGroup(SequenceGroup gp)
 475   {
 476     if (annotations == null || annotations.length == 0)
 477     {
 478       return;
 479     }
 480     // remove annotation very quickly
 481     AlignmentAnnotation[] t,
 482             todelete = new AlignmentAnnotation[annotations.length],
 483             tokeep = new AlignmentAnnotation[annotations.length];
 484     int i, p, k;
 485     if (gp == null)
 486     {
 487       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 488       {
 489         if (annotations[i].groupRef != null)
 490         {
 491           todelete[p++] = annotations[i];
 492         }
 493         else
 494         {
 495           tokeep[k++] = annotations[i];
 496         }
 497       }
 498     }
 499     else
 500     {
 501       for (i = 0, p = 0, k = 0; i < annotations.length; i++)
 502       {
 503         if (annotations[i].groupRef == gp)
 504         {
 505           todelete[p++] = annotations[i];
 506         }
 507         else
 508         {
 509           tokeep[k++] = annotations[i];
 510         }
 511       }
 512     }
 513     if (p > 0)
 514     {
 515       // clear out the group associated annotation.
 516       for (i = 0; i < p; i++)
 517       {
 518         unhookAnnotation(todelete[i]);
 519         todelete[i] = null;
 520       }
 521       t = new AlignmentAnnotation[k];
 522       for (i = 0; i < k; i++)
 523       {
 524         t[i] = tokeep[i];
 525       }
 526       annotations = t;
 527     }
 528   }
 529
 530   @Override
 531   public void deleteAllGroups()
 532   {
 533     synchronized (groups)
 534     {
 535       if (annotations != null)
 536       {
 537         removeAnnotationForGroup(null);
 538       }
 539       for (SequenceGroup sg : groups)
 540       {
 541         sg.setContext(null, false);
 542       }
 543       groups.clear();
 544     }
 545   }
 546
 547   /**    */
 548   @Override
 549   public void deleteGroup(SequenceGroup g)
 550   {
 551     synchronized (groups)
 552     {
 553       if (groups.contains(g))
 554       {
 555         removeAnnotationForGroup(g);
 556         groups.remove(g);
 557         g.setContext(null, false);
 558       }
 559     }
 560   }
 561
 562   /**    */
 563   @Override
 564   public SequenceI findName(String name)
 565   {
 566     return findName(name, false);
 567   }
 568
 569   /*
 570    * (non-Javadoc)
 571    *
 572    * @see jalview.datamodel.AlignmentI#findName(java.lang.String, boolean)
 573    */
 574   @Override
 575   public SequenceI findName(String token, boolean b)
 576   {
 577     return findName(null, token, b);
 578   }
 579
 580   /*
 581    * (non-Javadoc)
 582    *
 583    * @see jalview.datamodel.AlignmentI#findName(SequenceI, java.lang.String,
 584    * boolean)
 585    */
 586   @Override
 587   public SequenceI findName(SequenceI startAfter, String token, boolean b)
 588   {
 589
 590     int i = 0;
 591     SequenceI sq = null;
 592     String sqname = null;
 593     int nseq = sequences.size();
 594     if (startAfter != null)
 595     {
 596       // try to find the sequence in the alignment
 597       boolean matched = false;
 598       while (i < nseq)
 599       {
 600         if (getSequenceAt(i++) == startAfter)
 601         {
 602           matched = true;
 603           break;
 604         }
 605       }
 606       if (!matched)
 607       {
 608         i = 0;
 609       }
 610     }
 611     while (i < nseq)
 612     {
 613       sq = getSequenceAt(i);
 614       sqname = sq.getName();
 615       if (sqname.equals(token) // exact match
 616               || (b && // allow imperfect matches - case varies
 617                       (sqname.equalsIgnoreCase(token))))
 618       {
 619         return getSequenceAt(i);
 620       }
 621
 622       i++;
 623     }
 624
 625     return null;
 626   }
 627
 628   @Override
 629   public SequenceI[] findSequenceMatch(String name)
 630   {
 631     Vector matches = new Vector();
 632     int i = 0;
 633
 634     while (i < sequences.size())
 635     {
 636       if (getSequenceAt(i).getName().equals(name))
 637       {
 638         matches.addElement(getSequenceAt(i));
 639       }
 640       i++;
 641     }
 642
 643     SequenceI[] result = new SequenceI[matches.size()];
 644     for (i = 0; i < result.length; i++)
 645     {
 646       result[i] = (SequenceI) matches.elementAt(i);
 647     }
 648
 649     return result;
 650
 651   }
 652
 653   /*
 654    * (non-Javadoc)
 655    *
 656    * @see jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SequenceI)
 657    */
 658   @Override
 659   public int findIndex(SequenceI s)
 660   {
 661     int i = 0;
 662
 663     while (i < sequences.size())
 664     {
 665       if (s == getSequenceAt(i))
 666       {
 667         return i;
 668       }
 669
 670       i++;
 671     }
 672
 673     return -1;
 674   }
 675
 676   /*
 677    * (non-Javadoc)
 678    *
 679    * @see
 680    * jalview.datamodel.AlignmentI#findIndex(jalview.datamodel.SearchResults)
 681    */
 682   @Override
 683   public int findIndex(SearchResultsI results)
 684   {
 685     int i = 0;
 686
 687     while (i < sequences.size())
 688     {
 689       if (results.involvesSequence(getSequenceAt(i)))
 690       {
 691         return i;
 692       }
 693       i++;
 694     }
 695     return -1;
 696   }
 697
 698   @Override
 699   public int getHeight()
 700   {
 701     return sequences.size();
 702   }
 703
 704   @Override
 705   public int getAbsoluteHeight()
 706   {
 707     return sequences.size() + getHiddenSequences().getSize();
 708   }
 709
 710   @Override
 711   public int getWidth()
 712   {
 713     int maxLength = -1;
 714
 715     for (int i = 0; i < sequences.size(); i++)
 716     {
 717       maxLength = Math.max(maxLength, getSequenceAt(i).getLength());
 718     }
 719     return maxLength;
 720   }
 721
 722   @Override
 723   public int getVisibleWidth()
 724   {
 725     int w = getWidth();
 726     if (hiddenCols != null)
 727     {
 728       w -= hiddenCols.getSize();
 729     }
 730     return w;
 731   }
 732
 733   /**
 734    * DOCUMENT ME!
 735    *
 736    * @param gc
 737    *          DOCUMENT ME!
 738    */
 739   @Override
 740   public void setGapCharacter(char gc)
 741   {
 742     gapCharacter = gc;
 743     synchronized (sequences)
 744     {
 745       for (SequenceI seq : sequences)
 746       {
 747         seq.setSequence(seq.getSequenceAsString().replace('.', gc)
 748                 .replace('-', gc).replace(' ', gc));
 749       }
 750     }
 751   }
 752
 753   /**
 754    * DOCUMENT ME!
 755    *
 756    * @return DOCUMENT ME!
 757    */
 758   @Override
 759   public char getGapCharacter()
 760   {
 761     return gapCharacter;
 762   }
 763
 764   /*
 765    * (non-Javadoc)
 766    *
 767    * @see jalview.datamodel.AlignmentI#isAligned()
 768    */
 769   @Override
 770   public boolean isAligned()
 771   {
 772     return isAligned(false);
 773   }
 774
 775   /*
 776    * (non-Javadoc)
 777    *
 778    * @see jalview.datamodel.AlignmentI#isAligned(boolean)
 779    */
 780   @Override
 781   public boolean isAligned(boolean includeHidden)
 782   {
 783     int width = getWidth();
 784     if (hiddenSequences == null || hiddenSequences.getSize() == 0)
 785     {
 786       includeHidden = true; // no hidden sequences to check against.
 787     }
 788     for (int i = 0; i < sequences.size(); i++)
 789     {
 790       if (includeHidden || !hiddenSequences.isHidden(getSequenceAt(i)))
 791       {
 792         if (getSequenceAt(i).getLength() != width)
 793         {
 794           return false;
 795         }
 796       }
 797     }
 798
 799     return true;
 800   }
 801
 802   @Override
 803   public boolean isHidden(int alignmentIndex)
 804   {
 805     return (getHiddenSequences().getHiddenSequence(alignmentIndex) != null);
 806   }
 807
 808   /**
 809    * Delete all annotations, including auto-calculated if the flag is set true.
 810    * Returns true if at least one annotation was deleted, else false.
 811    *
 812    * @param includingAutoCalculated
 813    * @return
 814    */
 815   @Override
 816   public boolean deleteAllAnnotations(boolean includingAutoCalculated)
 817   {
 818     boolean result = false;
 819     for (AlignmentAnnotation alan : getAlignmentAnnotation())
 820     {
 821       if (!alan.autoCalculated || includingAutoCalculated)
 822       {
 823         deleteAnnotation(alan);
 824         result = true;
 825       }
 826     }
 827     return result;
 828   }
 829
 830   /*
 831    * (non-Javadoc)
 832    *
 833    * @seejalview.datamodel.AlignmentI#deleteAnnotation(jalview.datamodel.
 834    * AlignmentAnnotation)
 835    */
 836   @Override
 837   public boolean deleteAnnotation(AlignmentAnnotation aa)
 838   {
 839     return deleteAnnotation(aa, true);
 840   }
 841
 842   @Override
 843   public boolean deleteAnnotation(AlignmentAnnotation aa, boolean unhook)
 844   {
 845     int aSize = 1;
 846
 847     if (annotations != null)
 848     {
 849       aSize = annotations.length;
 850     }
 851
 852     if (aSize < 1)
 853     {
 854       return false;
 855     }
 856
 857     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize - 1];
 858
 859     boolean swap = false;
 860     int tIndex = 0;
 861
 862     for (int i = 0; i < aSize; i++)
 863     {
 864       if (annotations[i] == aa)
 865       {
 866         swap = true;
 867         continue;
 868       }
 869       if (tIndex < temp.length)
 870       {
 871         temp[tIndex++] = annotations[i];
 872       }
 873     }
 874
 875     if (swap)
 876     {
 877       annotations = temp;
 878       if (unhook)
 879       {
 880         unhookAnnotation(aa);
 881       }
 882     }
 883     return swap;
 884   }
 885
 886   /**
 887    * remove any object references associated with this annotation
 888    *
 889    * @param aa
 890    */
 891   private void unhookAnnotation(AlignmentAnnotation aa)
 892   {
 893     if (aa.sequenceRef != null)
 894     {
 895       aa.sequenceRef.removeAlignmentAnnotation(aa);
 896     }
 897     if (aa.groupRef != null)
 898     {
 899       // probably need to do more here in the future (post 2.5.0)
 900       aa.groupRef = null;
 901     }
 902   }
 903
 904   /*
 905    * (non-Javadoc)
 906    *
 907    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 908    * AlignmentAnnotation)
 909    */
 910   @Override
 911   public void addAnnotation(AlignmentAnnotation aa)
 912   {
 913     addAnnotation(aa, -1);
 914   }
 915
 916   /*
 917    * (non-Javadoc)
 918    *
 919    * @seejalview.datamodel.AlignmentI#addAnnotation(jalview.datamodel.
 920    * AlignmentAnnotation, int)
 921    */
 922   @Override
 923   public void addAnnotation(AlignmentAnnotation aa, int pos)
 924   {
 925     if (aa.getRNAStruc() != null)
 926     {
 927       hasRNAStructure = true;
 928     }
 929
 930     int aSize = 1;
 931     if (annotations != null)
 932     {
 933       aSize = annotations.length + 1;
 934     }
 935
 936     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 937     int i = 0;
 938     if (pos == -1 || pos >= aSize)
 939     {
 940       temp[aSize - 1] = aa;
 941     }
 942     else
 943     {
 944       temp[pos] = aa;
 945     }
 946     if (aSize > 1)
 947     {
 948       int p = 0;
 949       for (i = 0; i < (aSize - 1); i++, p++)
 950       {
 951         if (p == pos)
 952         {
 953           p++;
 954         }
 955         if (p < temp.length)
 956         {
 957           temp[p] = annotations[i];
 958         }
 959       }
 960     }
 961
 962     annotations = temp;
 963   }
 964
 965   @Override
 966   public void setAnnotationIndex(AlignmentAnnotation aa, int index)
 967   {
 968     if (aa == null || annotations == null || annotations.length - 1 < index)
 969     {
 970       return;
 971     }
 972
 973     int aSize = annotations.length;
 974     AlignmentAnnotation[] temp = new AlignmentAnnotation[aSize];
 975
 976     temp[index] = aa;
 977
 978     for (int i = 0; i < aSize; i++)
 979     {
 980       if (i == index)
 981       {
 982         continue;
 983       }
 984
 985       if (i < index)
 986       {
 987         temp[i] = annotations[i];
 988       }
 989       else
 990       {
 991         temp[i] = annotations[i - 1];
 992       }
 993     }
 994
 995     annotations = temp;
 996   }
 997
 998   @Override
 999   /**
1000    * returns all annotation on the alignment
1001    */
1002   public AlignmentAnnotation[] getAlignmentAnnotation()
1003   {
1004     return annotations;
1005   }
1006
1007   @Override
1008   public boolean isNucleotide()
1009   {
1010     return nucleotide;
1011   }
1012
1013   @Override
1014   public boolean hasRNAStructure()
1015   {
1016     // TODO can it happen that structure is removed from alignment?
1017     return hasRNAStructure;
1018   }
1019
1020   @Override
1021   public void setDataset(AlignmentI data)
1022   {
1023     if (dataset == null && data == null)
1024     {
1025       createDatasetAlignment();
1026     }
1027     else if (dataset == null && data != null)
1028     {
1029       if (data == this)
1030       {
1031         throw new IllegalArgumentException("Circular dataset reference");
1032       }
1033       if (!(data instanceof Alignment))
1034       {
1035         throw new Error(
1036                 "Implementation Error: jalview.datamodel.Alignment does not yet support other implementations of AlignmentI as its dataset reference");
1037       }
1038       dataset = (Alignment) data;
1039       for (int i = 0; i < getHeight(); i++)
1040       {
1041         SequenceI currentSeq = getSequenceAt(i);
1042         SequenceI dsq = currentSeq.getDatasetSequence();
1043         if (dsq == null)
1044         {
1045           dsq = currentSeq.createDatasetSequence();
1046           dataset.addSequence(dsq);
1047         }
1048         else
1049         {
1050           while (dsq.getDatasetSequence() != null)
1051           {
1052             dsq = dsq.getDatasetSequence();
1053           }
1054           if (dataset.findIndex(dsq) == -1)
1055           {
1056             dataset.addSequence(dsq);
1057           }
1058         }
1059       }
1060     }
1061     dataset.addAlignmentRef();
1062   }
1063
1064   /**
1065    * add dataset sequences to seq for currentSeq and any sequences it references
1066    */
1067   private void resolveAndAddDatasetSeq(SequenceI currentSeq,
1068           Set<SequenceI> seqs, boolean createDatasetSequence)
1069   {
1070     SequenceI alignedSeq = currentSeq;
1071     if (currentSeq.getDatasetSequence() != null)
1072     {
1073       currentSeq = currentSeq.getDatasetSequence();
1074     }
1075     else
1076     {
1077       if (createDatasetSequence)
1078       {
1079         currentSeq = currentSeq.createDatasetSequence();
1080       }
1081     }
1082
1083     List<SequenceI> toProcess = new ArrayList<>();
1084     toProcess.add(currentSeq);
1085     while (toProcess.size() > 0)
1086     {
1087       // use a queue ?
1088       SequenceI curDs = toProcess.remove(0);
1089
1090       if (!seqs.add(curDs))
1091       {
1092         continue;
1093       }
1094       // iterate over database references, making sure we add forward referenced
1095       // sequences
1096       if (curDs.getDBRefs() != null)
1097       {
1098         for (DBRefEntry dbr : curDs.getDBRefs())
1099         {
1100           if (dbr.getMap() != null && dbr.getMap().getTo() != null)
1101           {
1102             if (dbr.getMap().getTo() == alignedSeq)
1103             {
1104               /*
1105                * update mapping to be to the newly created dataset sequence
1106                */
1107               dbr.getMap().setTo(currentSeq);
1108             }
1109             if (dbr.getMap().getTo().getDatasetSequence() != null)
1110             {
1111               throw new Error("Implementation error: Map.getTo() for dbref "
1112                       + dbr + " from " + curDs.getName()
1113                       + " is not a dataset sequence.");
1114             }
1115             // we recurse to add all forward references to dataset sequences via
1116             // DBRefs/etc
1117             toProcess.add(dbr.getMap().getTo());
1118           }
1119         }
1120       }
1121     }
1122   }
1123
1124   /**
1125    * Creates a new dataset for this alignment. Can only be done once - if
1126    * dataset is not null this will not be performed.
1127    */
1128   public void createDatasetAlignment()
1129   {
1130     if (dataset != null)
1131     {
1132       return;
1133     }
1134     // try to avoid using SequenceI.equals at this stage, it will be expensive
1135     Set<SequenceI> seqs = new LinkedIdentityHashSet<>();
1136
1137     for (int i = 0; i < getHeight(); i++)
1138     {
1139       SequenceI currentSeq = getSequenceAt(i);
1140       resolveAndAddDatasetSeq(currentSeq, seqs, true);
1141     }
1142
1143     // verify all mappings are in dataset
1144     for (AlignedCodonFrame cf : codonFrameList)
1145     {
1146       for (SequenceToSequenceMapping ssm : cf.getMappings())
1147       {
1148         if (!seqs.contains(ssm.getFromSeq()))
1149         {
1150           resolveAndAddDatasetSeq(ssm.getFromSeq(), seqs, false);
1151         }
1152         if (!seqs.contains(ssm.getMapping().getTo()))
1153         {
1154           resolveAndAddDatasetSeq(ssm.getMapping().getTo(), seqs, false);
1155         }
1156       }
1157     }
1158     // finally construct dataset
1159     dataset = new Alignment(seqs.toArray(new SequenceI[seqs.size()]));
1160     // move mappings to the dataset alignment
1161     dataset.codonFrameList = this.codonFrameList;
1162     this.codonFrameList = null;
1163   }
1164
1165   /**
1166    * reference count for number of alignments referencing this one.
1167    */
1168   int alignmentRefs = 0;
1169
1170   /**
1171    * increase reference count to this alignment.
1172    */
1173   private void addAlignmentRef()
1174   {
1175     alignmentRefs++;
1176   }
1177
1178   @Override
1179   public Alignment getDataset()
1180   {
1181     return dataset;
1182   }
1183
1184   @Override
1185   public boolean padGaps()
1186   {
1187     boolean modified = false;
1188
1189     // Remove excess gaps from the end of alignment
1190     int maxLength = -1;
1191
1192     SequenceI current;
1193     int nseq = sequences.size();
1194     for (int i = 0; i < nseq; i++)
1195     {
1196       current = getSequenceAt(i);
1197       for (int j = current.getLength(); j > maxLength; j--)
1198       {
1199         if (j > maxLength
1200                 && !jalview.util.Comparison.isGap(current.getCharAt(j)))
1201         {
1202           maxLength = j;
1203           break;
1204         }
1205       }
1206     }
1207
1208     maxLength++;
1209
1210     int cLength;
1211     for (int i = 0; i < nseq; i++)
1212     {
1213       current = getSequenceAt(i);
1214       cLength = current.getLength();
1215
1216       if (cLength < maxLength)
1217       {
1218         current.insertCharAt(cLength, maxLength - cLength, gapCharacter);
1219         modified = true;
1220       }
1221       else if (current.getLength() > maxLength)
1222       {
1223         current.deleteChars(maxLength, current.getLength());
1224       }
1225     }
1226     return modified;
1227   }
1228
1229   /**
1230    * Justify the sequences to the left or right by deleting and inserting gaps
1231    * before the initial residue or after the terminal residue
1232    *
1233    * @param right
1234    *          true if alignment padded to right, false to justify to left
1235    * @return true if alignment was changed
1236    */
1237   @Override
1238   public boolean justify(boolean right)
1239   {
1240     boolean modified = false;
1241
1242     // Remove excess gaps from the end of alignment
1243     int maxLength = -1;
1244     int ends[] = new int[sequences.size() * 2];
1245     SequenceI current;
1246     for (int i = 0; i < sequences.size(); i++)
1247     {
1248       current = getSequenceAt(i);
1249       // This should really be a sequence method
1250       ends[i * 2] = current.findIndex(current.getStart());
1251       ends[i * 2 + 1] = current
1252               .findIndex(current.getStart() + current.getLength());
1253       boolean hitres = false;
1254       for (int j = 0, rs = 0, ssiz = current.getLength(); j < ssiz; j++)
1255       {
1256         if (!jalview.util.Comparison.isGap(current.getCharAt(j)))
1257         {
1258           if (!hitres)
1259           {
1260             ends[i * 2] = j;
1261             hitres = true;
1262           }
1263           else
1264           {
1265             ends[i * 2 + 1] = j;
1266             if (j - ends[i * 2] > maxLength)
1267             {
1268               maxLength = j - ends[i * 2];
1269             }
1270           }
1271         }
1272       }
1273     }
1274
1275     maxLength++;
1276     // now edit the flanking gaps to justify to either left or right
1277     int cLength, extent, diff;
1278     for (int i = 0; i < sequences.size(); i++)
1279     {
1280       current = getSequenceAt(i);
1281
1282       cLength = 1 + ends[i * 2 + 1] - ends[i * 2];
1283       diff = maxLength - cLength; // number of gaps to indent
1284       extent = current.getLength();
1285       if (right)
1286       {
1287         // right justify
1288         if (extent > ends[i * 2 + 1])
1289         {
1290           current.deleteChars(ends[i * 2 + 1] + 1, extent);
1291           modified = true;
1292         }
1293         if (ends[i * 2] > diff)
1294         {
1295           current.deleteChars(0, ends[i * 2] - diff);
1296           modified = true;
1297         }
1298         else
1299         {
1300           if (ends[i * 2] < diff)
1301           {
1302             current.insertCharAt(0, diff - ends[i * 2], gapCharacter);
1303             modified = true;
1304           }
1305         }
1306       }
1307       else
1308       {
1309         // left justify
1310         if (ends[i * 2] > 0)
1311         {
1312           current.deleteChars(0, ends[i * 2]);
1313           modified = true;
1314           ends[i * 2 + 1] -= ends[i * 2];
1315           extent -= ends[i * 2];
1316         }
1317         if (extent > maxLength)
1318         {
1319           current.deleteChars(maxLength + 1, extent);
1320           modified = true;
1321         }
1322         else
1323         {
1324           if (extent < maxLength)
1325           {
1326             current.insertCharAt(extent, maxLength - extent, gapCharacter);
1327             modified = true;
1328           }
1329         }
1330       }
1331     }
1332     return modified;
1333   }
1334
1335   @Override
1336   public HiddenSequences getHiddenSequences()
1337   {
1338     return hiddenSequences;
1339   }
1340
1341   @Override
1342   public HiddenColumns getHiddenColumns()
1343   {
1344     return hiddenCols;
1345   }
1346
1347   @Override
1348   public CigarArray getCompactAlignment()
1349   {
1350     synchronized (sequences)
1351     {
1352       SeqCigar alseqs[] = new SeqCigar[sequences.size()];
1353       int i = 0;
1354       for (SequenceI seq : sequences)
1355       {
1356         alseqs[i++] = new SeqCigar(seq);
1357       }
1358       CigarArray cal = new CigarArray(alseqs);
1359       cal.addOperation(CigarArray.M, getWidth());
1360       return cal;
1361     }
1362   }
1363
1364   @Override
1365   public void setProperty(Object key, Object value)
1366   {
1367     if (alignmentProperties == null)
1368     {
1369       alignmentProperties = new Hashtable();
1370     }
1371
1372     alignmentProperties.put(key, value);
1373   }
1374
1375   @Override
1376   public Object getProperty(Object key)
1377   {
1378     if (alignmentProperties != null)
1379     {
1380       return alignmentProperties.get(key);
1381     }
1382     else
1383     {
1384       return null;
1385     }
1386   }
1387
1388   @Override
1389   public Hashtable getProperties()
1390   {
1391     return alignmentProperties;
1392   }
1393
1394   /**
1395    * Adds the given mapping to the stored set. Note this may be held on the
1396    * dataset alignment.
1397    */
1398   @Override
1399   public void addCodonFrame(AlignedCodonFrame codons)
1400   {
1401     List<AlignedCodonFrame> acfs = getCodonFrames();
1402     if (codons != null && acfs != null && !acfs.contains(codons))
1403     {
1404       acfs.add(codons);
1405     }
1406   }
1407
1408   /*
1409    * (non-Javadoc)
1410    *
1411    * @see
1412    * jalview.datamodel.AlignmentI#getCodonFrame(jalview.datamodel.SequenceI)
1413    */
1414   @Override
1415   public List<AlignedCodonFrame> getCodonFrame(SequenceI seq)
1416   {
1417     if (seq == null)
1418     {
1419       return null;
1420     }
1421     List<AlignedCodonFrame> cframes = new ArrayList<>();
1422     for (AlignedCodonFrame acf : getCodonFrames())
1423     {
1424       if (acf.involvesSequence(seq))
1425       {
1426         cframes.add(acf);
1427       }
1428     }
1429     return cframes;
1430   }
1431
1432   /**
1433    * Sets the codon frame mappings (replacing any existing mappings). Note the
1434    * mappings are set on the dataset alignment instead if there is one.
1435    *
1436    * @see jalview.datamodel.AlignmentI#setCodonFrames()
1437    */
1438   @Override
1439   public void setCodonFrames(List<AlignedCodonFrame> acfs)
1440   {
1441     if (dataset != null)
1442     {
1443       dataset.setCodonFrames(acfs);
1444     }
1445     else
1446     {
1447       this.codonFrameList = acfs;
1448     }
1449   }
1450
1451   /**
1452    * Returns the set of codon frame mappings. Any changes to the returned set
1453    * will affect the alignment. The mappings are held on (and read from) the
1454    * dataset alignment if there is one.
1455    *
1456    * @see jalview.datamodel.AlignmentI#getCodonFrames()
1457    */
1458   @Override
1459   public List<AlignedCodonFrame> getCodonFrames()
1460   {
1461     // TODO: Fix this method to fix failing AlignedCodonFrame tests
1462     // this behaviour is currently incorrect. method should return codon frames
1463     // for just the alignment,
1464     // selected from dataset
1465     return dataset != null ? dataset.getCodonFrames() : codonFrameList;
1466   }
1467
1468   /**
1469    * Removes the given mapping from the stored set. Note that the mappings are
1470    * held on the dataset alignment if there is one.
1471    */
1472   @Override
1473   public boolean removeCodonFrame(AlignedCodonFrame codons)
1474   {
1475     List<AlignedCodonFrame> acfs = getCodonFrames();
1476     if (codons == null || acfs == null)
1477     {
1478       return false;
1479     }
1480     return acfs.remove(codons);
1481   }
1482
1483   @Override
1484   public void append(AlignmentI toappend)
1485   {
1486     // TODO JAL-1270 needs test coverage
1487     // currently tested for use in jalview.gui.SequenceFetcher
1488     char oldc = toappend.getGapCharacter();
1489     boolean samegap = oldc == getGapCharacter();
1490     boolean hashidden = toappend.getHiddenSequences() != null
1491             && toappend.getHiddenSequences().hiddenSequences != null;
1492     // get all sequences including any hidden ones
1493     List<SequenceI> sqs = (hashidden)
1494             ? toappend.getHiddenSequences().getFullAlignment()
1495                     .getSequences()
1496             : toappend.getSequences();
1497     if (sqs != null)
1498     {
1499       // avoid self append deadlock by
1500       List<SequenceI> toappendsq = new ArrayList<>();
1501       synchronized (sqs)
1502       {
1503         for (SequenceI addedsq : sqs)
1504         {
1505           if (!samegap)
1506           {
1507             addedsq.replace(oldc, gapCharacter);
1508           }
1509           toappendsq.add(addedsq);
1510         }
1511       }
1512       for (SequenceI addedsq : toappendsq)
1513       {
1514         addSequence(addedsq);
1515       }
1516     }
1517     AlignmentAnnotation[] alan = toappend.getAlignmentAnnotation();
1518     for (int a = 0; alan != null && a < alan.length; a++)
1519     {
1520       addAnnotation(alan[a]);
1521     }
1522
1523     // use add method
1524     getCodonFrames().addAll(toappend.getCodonFrames());
1525
1526     List<SequenceGroup> sg = toappend.getGroups();
1527     if (sg != null)
1528     {
1529       for (SequenceGroup _sg : sg)
1530       {
1531         addGroup(_sg);
1532       }
1533     }
1534     if (toappend.getHiddenSequences() != null)
1535     {
1536       HiddenSequences hs = toappend.getHiddenSequences();
1537       if (hiddenSequences == null)
1538       {
1539         hiddenSequences = new HiddenSequences(this);
1540       }
1541       if (hs.hiddenSequences != null)
1542       {
1543         for (int s = 0; s < hs.hiddenSequences.length; s++)
1544         {
1545           // hide the newly appended sequence in the alignment
1546           if (hs.hiddenSequences[s] != null)
1547           {
1548             hiddenSequences.hideSequence(hs.hiddenSequences[s]);
1549           }
1550         }
1551       }
1552     }
1553     if (toappend.getProperties() != null)
1554     {
1555       // we really can't do very much here - just try to concatenate strings
1556       // where property collisions occur.
1557       Enumeration key = toappend.getProperties().keys();
1558       while (key.hasMoreElements())
1559       {
1560         Object k = key.nextElement();
1561         Object ourval = this.getProperty(k);
1562         Object toapprop = toappend.getProperty(k);
1563         if (ourval != null)
1564         {
1565           if (ourval.getClass().equals(toapprop.getClass())
1566                   && !ourval.equals(toapprop))
1567           {
1568             if (ourval instanceof String)
1569             {
1570               // append strings
1571               this.setProperty(k,
1572                       ((String) ourval) + "; " + ((String) toapprop));
1573             }
1574             else
1575             {
1576               if (ourval instanceof Vector)
1577               {
1578                 // append vectors
1579                 Enumeration theirv = ((Vector) toapprop).elements();
1580                 while (theirv.hasMoreElements())
1581                 {
1582                   ((Vector) ourval).addElement(theirv);
1583                 }
1584               }
1585             }
1586           }
1587         }
1588         else
1589         {
1590           // just add new property directly
1591           setProperty(k, toapprop);
1592         }
1593
1594       }
1595     }
1596   }
1597
1598   @Override
1599   public AlignmentAnnotation findOrCreateAnnotation(String name,
1600           String calcId, boolean autoCalc, SequenceI seqRef,
1601           SequenceGroup groupRef)
1602   {
1603     if (annotations != null)
1604     {
1605       for (AlignmentAnnotation annot : getAlignmentAnnotation())
1606       {
1607         if (annot.autoCalculated == autoCalc && (name.equals(annot.label))
1608                 && (calcId == null || annot.getCalcId().equals(calcId))
1609                 && annot.sequenceRef == seqRef
1610                 && annot.groupRef == groupRef)
1611         {
1612           return annot;
1613         }
1614       }
1615     }
1616     AlignmentAnnotation annot = new AlignmentAnnotation(name, name,
1617             new Annotation[1], 0f, 0f, AlignmentAnnotation.BAR_GRAPH);
1618     annot.hasText = false;
1619     if (calcId != null)
1620     {
1621       annot.setCalcId(new String(calcId));
1622     }
1623     annot.autoCalculated = autoCalc;
1624     if (seqRef != null)
1625     {
1626       annot.setSequenceRef(seqRef);
1627     }
1628     annot.groupRef = groupRef;
1629     addAnnotation(annot);
1630
1631     return annot;
1632   }
1633
1634   @Override
1635   public Iterable<AlignmentAnnotation> findAnnotation(String calcId)
1636   {
1637     AlignmentAnnotation[] alignmentAnnotation = getAlignmentAnnotation();
1638     if (alignmentAnnotation != null)
1639     {
1640       return AlignmentAnnotation.findAnnotation(
1641               Arrays.asList(getAlignmentAnnotation()), calcId);
1642     }
1643     return Arrays.asList(new AlignmentAnnotation[] {});
1644   }
1645
1646   @Override
1647   public Iterable<AlignmentAnnotation> findAnnotations(SequenceI seq,
1648           String calcId, String label)
1649   {
1650     return AlignmentAnnotation.findAnnotations(
1651             Arrays.asList(getAlignmentAnnotation()), seq, calcId, label);
1652   }
1653
1654   @Override
1655   public void moveSelectedSequencesByOne(SequenceGroup sg,
1656           Map<SequenceI, SequenceCollectionI> map, boolean up)
1657   {
1658     synchronized (sequences)
1659     {
1660       if (up)
1661       {
1662
1663         for (int i = 1, iSize = sequences.size(); i < iSize; i++)
1664         {
1665           SequenceI seq = sequences.get(i);
1666           if (!sg.getSequences(map).contains(seq))
1667           {
1668             continue;
1669           }
1670
1671           SequenceI temp = sequences.get(i - 1);
1672           if (sg.getSequences(null).contains(temp))
1673           {
1674             continue;
1675           }
1676
1677           sequences.set(i, temp);
1678           sequences.set(i - 1, seq);
1679         }
1680       }
1681       else
1682       {
1683         for (int i = sequences.size() - 2; i > -1; i--)
1684         {
1685           SequenceI seq = sequences.get(i);
1686           if (!sg.getSequences(map).contains(seq))
1687           {
1688             continue;
1689           }
1690
1691           SequenceI temp = sequences.get(i + 1);
1692           if (sg.getSequences(map).contains(temp))
1693           {
1694             continue;
1695           }
1696
1697           sequences.set(i, temp);
1698           sequences.set(i + 1, seq);
1699         }
1700       }
1701
1702     }
1703   }
1704
1705   @Override
1706   public void validateAnnotation(AlignmentAnnotation alignmentAnnotation)
1707   {
1708     alignmentAnnotation.validateRangeAndDisplay();
1709     if (isNucleotide() && alignmentAnnotation.isValidStruc())
1710     {
1711       hasRNAStructure = true;
1712     }
1713   }
1714
1715   private SequenceI seqrep = null;
1716
1717   /**
1718    *
1719    * @return the representative sequence for this group
1720    */
1721   @Override
1722   public SequenceI getSeqrep()
1723   {
1724     return seqrep;
1725   }
1726
1727   /**
1728    * set the representative sequence for this group. Note - this affects the
1729    * interpretation of the Hidereps attribute.
1730    *
1731    * @param seqrep
1732    *          the seqrep to set (null means no sequence representative)
1733    */
1734   @Override
1735   public void setSeqrep(SequenceI seqrep)
1736   {
1737     this.seqrep = seqrep;
1738   }
1739
1740   /**
1741    *
1742    * @return true if group has a sequence representative
1743    */
1744   @Override
1745   public boolean hasSeqrep()
1746   {
1747     return seqrep != null;
1748   }
1749
1750   @Override
1751   public int getEndRes()
1752   {
1753     return getWidth() - 1;
1754   }
1755
1756   @Override
1757   public int getStartRes()
1758   {
1759     return 0;
1760   }
1761
1762   /*
1763    * In the case of AlignmentI - returns the dataset for the alignment, if set
1764    * (non-Javadoc)
1765    *
1766    * @see jalview.datamodel.AnnotatedCollectionI#getContext()
1767    */
1768   @Override
1769   public AnnotatedCollectionI getContext()
1770   {
1771     return dataset;
1772   }
1773
1774   /**
1775    * Align this alignment like the given (mapped) one.
1776    */
1777   @Override
1778   public int alignAs(AlignmentI al)
1779   {
1780     /*
1781      * Currently retains unmapped gaps (in introns), regaps mapped regions
1782      * (exons)
1783      */
1784     return alignAs(al, false, true);
1785   }
1786
1787   /**
1788    * Align this alignment 'the same as' the given one. Mapped sequences only are
1789    * realigned. If both of the same type (nucleotide/protein) then align both
1790    * identically. If this is nucleotide and the other is protein, make 3 gaps
1791    * for each gap in the protein sequences. If this is protein and the other is
1792    * nucleotide, insert a gap for each 3 gaps (or part thereof) between
1793    * nucleotide bases. If this is protein and the other is nucleotide, gaps
1794    * protein to match the relative ordering of codons in the nucleotide.
1795    *
1796    * Parameters control whether gaps in exon (mapped) and intron (unmapped)
1797    * regions are preserved. Gaps that connect introns to exons are treated
1798    * conservatively, i.e. only preserved if both intron and exon gaps are
1799    * preserved. TODO: check caveats below where the implementation fails
1800    *
1801    * @param al
1802    *          - must have same dataset, and sequences in al must have equivalent
1803    *          dataset sequence and start/end bounds under given mapping
1804    * @param preserveMappedGaps
1805    *          if true, gaps within and between mapped codons are preserved
1806    * @param preserveUnmappedGaps
1807    *          if true, gaps within and between unmapped codons are preserved
1808    */
1809   // @Override
1810   public int alignAs(AlignmentI al, boolean preserveMappedGaps,
1811           boolean preserveUnmappedGaps)
1812   {
1813     // TODO should this method signature be the one in the interface?
1814     // JBPComment - yes - neither flag is used, so should be deleted.
1815     boolean thisIsNucleotide = this.isNucleotide();
1816     boolean thatIsProtein = !al.isNucleotide();
1817     if (!thatIsProtein && !thisIsNucleotide)
1818     {
1819       return AlignmentUtils.alignProteinAsDna(this, al);
1820     }
1821     else if (thatIsProtein && thisIsNucleotide)
1822     {
1823       return AlignmentUtils.alignCdsAsProtein(this, al);
1824     }
1825     return AlignmentUtils.alignAs(this, al);
1826   }
1827
1828   /**
1829    * Returns the alignment in Fasta format. Behaviour of this method is not
1830    * guaranteed between versions.
1831    */
1832   @Override
1833   public String toString()
1834   {
1835     return new FastaFile().print(getSequencesArray(), true);
1836   }
1837
1838   /**
1839    * Returns the set of distinct sequence names. No ordering is guaranteed.
1840    */
1841   @Override
1842   public Set<String> getSequenceNames()
1843   {
1844     Set<String> names = new HashSet<>();
1845     for (SequenceI seq : getSequences())
1846     {
1847       names.add(seq.getName());
1848     }
1849     return names;
1850   }
1851
1852   @Override
1853   public boolean hasValidSequence()
1854   {
1855     boolean hasValidSeq = false;
1856     for (SequenceI seq : getSequences())
1857     {
1858       if ((seq.getEnd() - seq.getStart()) > 0)
1859       {
1860         hasValidSeq = true;
1861         break;
1862       }
1863     }
1864     return hasValidSeq;
1865   }
1866
1867   /**
1868    * Update any mappings to 'virtual' sequences to compatible real ones, if
1869    * present in the added sequences. Returns a count of mappings updated.
1870    *
1871    * @param seqs
1872    * @return
1873    */
1874   @Override
1875   public int realiseMappings(List<SequenceI> seqs)
1876   {
1877     int count = 0;
1878     for (SequenceI seq : seqs)
1879     {
1880       for (AlignedCodonFrame mapping : getCodonFrames())
1881       {
1882         count += mapping.realiseWith(seq);
1883       }
1884     }
1885     return count;
1886   }
1887
1888   /**
1889    * Returns the first AlignedCodonFrame that has a mapping between the given
1890    * dataset sequences
1891    *
1892    * @param mapFrom
1893    * @param mapTo
1894    * @return
1895    */
1896   @Override
1897   public AlignedCodonFrame getMapping(SequenceI mapFrom, SequenceI mapTo)
1898   {
1899     for (AlignedCodonFrame acf : getCodonFrames())
1900     {
1901       if (acf.getAaForDnaSeq(mapFrom) == mapTo)
1902       {
1903         return acf;
1904       }
1905     }
1906     return null;
1907   }
1908
1909   @Override
1910   public boolean setHiddenColumns(HiddenColumns cols)
1911   {
1912     boolean changed = cols == null ? hiddenCols != null
1913             : !cols.equals(hiddenCols);
1914     hiddenCols = cols;
1915     return changed;
1916   }
1917
1918   @Override
1919   public void setupJPredAlignment()
1920   {
1921     SequenceI repseq = getSequenceAt(0);
1922     setSeqrep(repseq);
1923     HiddenColumns cs = new HiddenColumns();
1924     cs.hideList(repseq.getInsertions());
1925     setHiddenColumns(cs);
1926   }
1927
1928   @Override
1929   public HiddenColumns propagateInsertions(SequenceI profileseq,
1930           AlignmentView input)
1931   {
1932     int profsqpos = 0;
1933
1934     char gc = getGapCharacter();
1935     Object[] alandhidden = input.getAlignmentAndHiddenColumns(gc);
1936     HiddenColumns nview = (HiddenColumns) alandhidden[1];
1937     SequenceI origseq = ((SequenceI[]) alandhidden[0])[profsqpos];
1938     return propagateInsertions(profileseq, origseq, nview);
1939   }
1940
1941   /**
1942    *
1943    * @param profileseq
1944    *          sequence in al which corresponds to origseq
1945    * @param al
1946    *          alignment which is to have gaps inserted into it
1947    * @param origseq
1948    *          sequence corresponding to profileseq which defines gap map for
1949    *          modifying al
1950    */
1951   private HiddenColumns propagateInsertions(SequenceI profileseq,
1952           SequenceI origseq, HiddenColumns hc)
1953   {
1954     // take the set of hidden columns, and the set of gaps in origseq,
1955     // and remove all the hidden gaps from hiddenColumns
1956
1957     // first get the gaps as a Bitset
1958     // then calculate hidden ^ not(gap)
1959     BitSet gaps = origseq.gapBitset();
1960     hc.andNot(gaps);
1961
1962     // for each sequence in the alignment, except the profile sequence,
1963     // insert gaps corresponding to each hidden region but where each hidden
1964     // column region is shifted backwards by the number of preceding visible
1965     // gaps update hidden columns at the same time
1966     HiddenColumns newhidden = new HiddenColumns();
1967
1968     int numGapsBefore = 0;
1969     int gapPosition = 0;
1970     Iterator<int[]> it = hc.iterator();
1971     while (it.hasNext())
1972     {
1973       int[] region = it.next();
1974
1975       // get region coordinates accounting for gaps
1976       // we can rely on gaps not being *in* hidden regions because we already
1977       // removed those
1978       while (gapPosition < region[0])
1979       {
1980         gapPosition++;
1981         if (gaps.get(gapPosition))
1982         {
1983           numGapsBefore++;
1984         }
1985       }
1986
1987       int left = region[0] - numGapsBefore;
1988       int right = region[1] - numGapsBefore;
1989
1990       newhidden.hideColumns(left, right);
1991       padGaps(left, right, profileseq);
1992     }
1993     return newhidden;
1994   }
1995
1996   /**
1997    * Pad gaps in all sequences in alignment except profileseq
1998    *
1999    * @param left
2000    *          position of first gap to insert
2001    * @param right
2002    *          position of last gap to insert
2003    * @param profileseq
2004    *          sequence not to pad
2005    */
2006   private void padGaps(int left, int right, SequenceI profileseq)
2007   {
2008     char gc = getGapCharacter();
2009
2010     // make a string with number of gaps = length of hidden region
2011     StringBuilder sb = new StringBuilder();
2012     for (int g = 0; g < right - left + 1; g++)
2013     {
2014       sb.append(gc);
2015     }
2016
2017     // loop over the sequences and pad with gaps where required
2018     for (int s = 0, ns = getHeight(); s < ns; s++)
2019     {
2020       SequenceI sqobj = getSequenceAt(s);
2021       if ((sqobj != profileseq) && (sqobj.getLength() >= left))
2022       {
2023         String sq = sqobj.getSequenceAsString();
2024         sqobj.setSequence(
2025                 sq.substring(0, left) + sb.toString() + sq.substring(left));
2026       }
2027     }
2028   }
2029
2030 }