src/jalview/datamodel/Sequence.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.AlignSeq;
  24 import jalview.api.DBRefEntryI;
  25 import jalview.datamodel.features.SequenceFeatures;
  26 import jalview.util.Comparison;
  27 import jalview.util.DBRefUtils;
  28 import jalview.util.MapList;
  29 import jalview.util.StringUtils;
  30
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Collections;
  34 import java.util.Enumeration;
  35 import java.util.List;
  36 import java.util.Vector;
  37
  38 import fr.orsay.lri.varna.models.rna.RNA;
  39
  40 /**
  41  *
  42  * Implements the SequenceI interface for a char[] based sequence object.
  43  *
  44  * @author $author$
  45  * @version $Revision$
  46  */
  47 public class Sequence extends ASequence implements SequenceI
  48 {
  49   SequenceI datasetSequence;
  50
  51   String name;
  52
  53   private char[] sequence;
  54
  55   String description;
  56
  57   int start;
  58
  59   int end;
  60
  61   Vector<PDBEntry> pdbIds;
  62
  63   String vamsasId;
  64
  65   DBRefEntry[] dbrefs;
  66
  67   RNA rna;
  68
  69   /**
  70    * This annotation is displayed below the alignment but the positions are tied
  71    * to the residues of this sequence
  72    *
  73    * TODO: change to List<>
  74    */
  75   Vector<AlignmentAnnotation> annotation;
  76
  77   /**
  78    * The index of the sequence in a MSA
  79    */
  80   int index = -1;
  81
  82   /** array of sequence features - may not be null for a valid sequence object */
  83   public SequenceFeature[] sequenceFeatures;
  84
  85   private SequenceFeatures sequenceFeatureStore;
  86
  87   /**
  88    * Creates a new Sequence object.
  89    *
  90    * @param name
  91    *          display name string
  92    * @param sequence
  93    *          string to form a possibly gapped sequence out of
  94    * @param start
  95    *          first position of non-gap residue in the sequence
  96    * @param end
  97    *          last position of ungapped residues (nearly always only used for
  98    *          display purposes)
  99    */
 100   public Sequence(String name, String sequence, int start, int end)
 101   {
 102     initSeqAndName(name, sequence.toCharArray(), start, end);
 103   }
 104
 105   public Sequence(String name, char[] sequence, int start, int end)
 106   {
 107     initSeqAndName(name, sequence, start, end);
 108   }
 109
 110   /**
 111    * Stage 1 constructor - assign name, sequence, and set start and end fields.
 112    * start and end are updated values from name2 if it ends with /start-end
 113    *
 114    * @param name2
 115    * @param sequence2
 116    * @param start2
 117    * @param end2
 118    */
 119   protected void initSeqAndName(String name2, char[] sequence2, int start2,
 120           int end2)
 121   {
 122     this.name = name2;
 123     this.sequence = sequence2;
 124     this.start = start2;
 125     this.end = end2;
 126     sequenceFeatureStore = new SequenceFeatures();
 127     parseId();
 128     checkValidRange();
 129   }
 130
 131   com.stevesoft.pat.Regex limitrx = new com.stevesoft.pat.Regex(
 132           "[/][0-9]{1,}[-][0-9]{1,}$");
 133
 134   com.stevesoft.pat.Regex endrx = new com.stevesoft.pat.Regex("[0-9]{1,}$");
 135
 136   void parseId()
 137   {
 138     if (name == null)
 139     {
 140       System.err
 141               .println("POSSIBLE IMPLEMENTATION ERROR: null sequence name passed to constructor.");
 142       name = "";
 143     }
 144     // Does sequence have the /start-end signature?
 145     if (limitrx.search(name))
 146     {
 147       name = limitrx.left();
 148       endrx.search(limitrx.stringMatched());
 149       setStart(Integer.parseInt(limitrx.stringMatched().substring(1,
 150               endrx.matchedFrom() - 1)));
 151       setEnd(Integer.parseInt(endrx.stringMatched()));
 152     }
 153   }
 154
 155   void checkValidRange()
 156   {
 157     // Note: JAL-774 :
 158     // http://issues.jalview.org/browse/JAL-774?focusedCommentId=11239&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-11239
 159     {
 160       int endRes = 0;
 161       for (int j = 0; j < sequence.length; j++)
 162       {
 163         if (!jalview.util.Comparison.isGap(sequence[j]))
 164         {
 165           endRes++;
 166         }
 167       }
 168       if (endRes > 0)
 169       {
 170         endRes += start - 1;
 171       }
 172
 173       if (end < endRes)
 174       {
 175         end = endRes;
 176       }
 177     }
 178
 179   }
 180
 181   /**
 182    * Creates a new Sequence object.
 183    *
 184    * @param name
 185    *          DOCUMENT ME!
 186    * @param sequence
 187    *          DOCUMENT ME!
 188    */
 189   public Sequence(String name, String sequence)
 190   {
 191     this(name, sequence, 1, -1);
 192   }
 193
 194   /**
 195    * Creates a new Sequence object with new AlignmentAnnotations but inherits
 196    * any existing dataset sequence reference. If non exists, everything is
 197    * copied.
 198    *
 199    * @param seq
 200    *          if seq is a dataset sequence, behaves like a plain old copy
 201    *          constructor
 202    */
 203   public Sequence(SequenceI seq)
 204   {
 205     this(seq, seq.getAnnotation());
 206   }
 207
 208   /**
 209    * Create a new sequence object with new features, DBRefEntries, and PDBIds
 210    * but inherits any existing dataset sequence reference, and duplicate of any
 211    * annotation that is present in the given annotation array.
 212    *
 213    * @param seq
 214    *          the sequence to be copied
 215    * @param alAnnotation
 216    *          an array of annotation including some associated with seq
 217    */
 218   public Sequence(SequenceI seq, AlignmentAnnotation[] alAnnotation)
 219   {
 220     initSeqFrom(seq, alAnnotation);
 221
 222   }
 223
 224   /**
 225    * does the heavy lifting when cloning a dataset sequence, or coping data from
 226    * dataset to a new derived sequence.
 227    *
 228    * @param seq
 229    *          - source of attributes.
 230    * @param alAnnotation
 231    *          - alignment annotation present on seq that should be copied onto
 232    *          this sequence
 233    */
 234   protected void initSeqFrom(SequenceI seq,
 235           AlignmentAnnotation[] alAnnotation)
 236   {
 237     {
 238       char[] oseq = seq.getSequence();
 239       initSeqAndName(seq.getName(), Arrays.copyOf(oseq, oseq.length),
 240               seq.getStart(), seq.getEnd());
 241     }
 242     description = seq.getDescription();
 243     if (seq != datasetSequence)
 244     {
 245       setDatasetSequence(seq.getDatasetSequence());
 246     }
 247     if (datasetSequence == null && seq.getDBRefs() != null)
 248     {
 249       // only copy DBRefs and seqfeatures if we really are a dataset sequence
 250       DBRefEntry[] dbr = seq.getDBRefs();
 251       for (int i = 0; i < dbr.length; i++)
 252       {
 253         addDBRef(new DBRefEntry(dbr[i]));
 254       }
 255       if (seq.getSequenceFeatures() != null)
 256       {
 257         SequenceFeature[] sf = seq.getSequenceFeatures();
 258         for (int i = 0; i < sf.length; i++)
 259         {
 260           addSequenceFeature(new SequenceFeature(sf[i]));
 261         }
 262       }
 263     }
 264     if (seq.getAnnotation() != null)
 265     {
 266       AlignmentAnnotation[] sqann = seq.getAnnotation();
 267       for (int i = 0; i < sqann.length; i++)
 268       {
 269         if (sqann[i] == null)
 270         {
 271           continue;
 272         }
 273         boolean found = (alAnnotation == null);
 274         if (!found)
 275         {
 276           for (int apos = 0; !found && apos < alAnnotation.length; apos++)
 277           {
 278             found = (alAnnotation[apos] == sqann[i]);
 279           }
 280         }
 281         if (found)
 282         {
 283           // only copy the given annotation
 284           AlignmentAnnotation newann = new AlignmentAnnotation(sqann[i]);
 285           addAlignmentAnnotation(newann);
 286         }
 287       }
 288     }
 289     if (seq.getAllPDBEntries() != null)
 290     {
 291       Vector<PDBEntry> ids = seq.getAllPDBEntries();
 292       for (PDBEntry pdb : ids)
 293       {
 294         this.addPDBId(new PDBEntry(pdb));
 295       }
 296     }
 297   }
 298
 299   @Override
 300   public void setSequenceFeatures(SequenceFeature[] features)
 301   {
 302     if (datasetSequence == null)
 303     {
 304       sequenceFeatures = features;
 305     }
 306     else
 307     {
 308       if (datasetSequence.getSequenceFeatures() != features
 309               && datasetSequence.getSequenceFeatures() != null
 310               && datasetSequence.getSequenceFeatures().length > 0)
 311       {
 312         new Exception(
 313                 "Warning: JAL-2046 side effect ? Possible implementation error: overwriting dataset sequence features by setting sequence features on alignment")
 314                 .printStackTrace();
 315       }
 316       datasetSequence.setSequenceFeatures(features);
 317     }
 318   }
 319
 320   @Override
 321   public synchronized boolean addSequenceFeature(SequenceFeature sf)
 322   {
 323     if (sequenceFeatures == null && datasetSequence != null)
 324     {
 325       return datasetSequence.addSequenceFeature(sf);
 326     }
 327     if (sequenceFeatures == null)
 328     {
 329       sequenceFeatures = new SequenceFeature[0];
 330     }
 331
 332     for (int i = 0; i < sequenceFeatures.length; i++)
 333     {
 334       if (sequenceFeatures[i].equals(sf))
 335       {
 336         return false;
 337       }
 338     }
 339
 340     SequenceFeature[] temp = new SequenceFeature[sequenceFeatures.length + 1];
 341     System.arraycopy(sequenceFeatures, 0, temp, 0, sequenceFeatures.length);
 342     temp[sequenceFeatures.length] = sf;
 343
 344     sequenceFeatures = temp;
 345
 346     sequenceFeatureStore.add(sf);
 347     return true;
 348   }
 349
 350   @Override
 351   public void deleteFeature(SequenceFeature sf)
 352   {
 353     if (sequenceFeatures == null)
 354     {
 355       if (datasetSequence != null)
 356       {
 357         datasetSequence.deleteFeature(sf);
 358       }
 359       return;
 360     }
 361
 362     int index = 0;
 363     for (index = 0; index < sequenceFeatures.length; index++)
 364     {
 365       if (sequenceFeatures[index].equals(sf))
 366       {
 367         break;
 368       }
 369     }
 370
 371     if (index == sequenceFeatures.length)
 372     {
 373       return;
 374     }
 375
 376     int sfLength = sequenceFeatures.length;
 377     if (sfLength < 2)
 378     {
 379       sequenceFeatures = null;
 380     }
 381     else
 382     {
 383       SequenceFeature[] temp = new SequenceFeature[sfLength - 1];
 384       System.arraycopy(sequenceFeatures, 0, temp, 0, index);
 385
 386       if (index < sfLength)
 387       {
 388         System.arraycopy(sequenceFeatures, index + 1, temp, index,
 389                 sequenceFeatures.length - index - 1);
 390       }
 391
 392       sequenceFeatures = temp;
 393     }
 394   }
 395
 396   /**
 397    * Returns the sequence features (if any), looking first on the sequence, then
 398    * on its dataset sequence, and so on until a non-null value is found (or
 399    * none). This supports retrieval of sequence features stored on the sequence
 400    * (as in the applet) or on the dataset sequence (as in the Desktop version).
 401    *
 402    * @return
 403    */
 404   @Override
 405   public SequenceFeature[] getSequenceFeatures()
 406   {
 407     SequenceFeature[] features = sequenceFeatures;
 408
 409     SequenceI seq = this;
 410     int count = 0; // failsafe against loop in sequence.datasetsequence...
 411     while (features == null && seq.getDatasetSequence() != null
 412             && count++ < 10)
 413     {
 414       seq = seq.getDatasetSequence();
 415       features = ((Sequence) seq).sequenceFeatures;
 416     }
 417     return features;
 418   }
 419
 420   @Override
 421   public boolean addPDBId(PDBEntry entry)
 422   {
 423     if (pdbIds == null)
 424     {
 425       pdbIds = new Vector<PDBEntry>();
 426       pdbIds.add(entry);
 427       return true;
 428     }
 429
 430     for (PDBEntry pdbe : pdbIds)
 431     {
 432       if (pdbe.updateFrom(entry))
 433       {
 434         return false;
 435       }
 436     }
 437     pdbIds.addElement(entry);
 438     return true;
 439   }
 440
 441   /**
 442    * DOCUMENT ME!
 443    *
 444    * @param id
 445    *          DOCUMENT ME!
 446    */
 447   @Override
 448   public void setPDBId(Vector<PDBEntry> id)
 449   {
 450     pdbIds = id;
 451   }
 452
 453   /**
 454    * DOCUMENT ME!
 455    *
 456    * @return DOCUMENT ME!
 457    */
 458   @Override
 459   public Vector<PDBEntry> getAllPDBEntries()
 460   {
 461     return pdbIds == null ? new Vector<PDBEntry>() : pdbIds;
 462   }
 463
 464   /**
 465    * DOCUMENT ME!
 466    *
 467    * @return DOCUMENT ME!
 468    */
 469   @Override
 470   public String getDisplayId(boolean jvsuffix)
 471   {
 472     StringBuffer result = new StringBuffer(name);
 473     if (jvsuffix)
 474     {
 475       result.append("/" + start + "-" + end);
 476     }
 477
 478     return result.toString();
 479   }
 480
 481   /**
 482    * DOCUMENT ME!
 483    *
 484    * @param name
 485    *          DOCUMENT ME!
 486    */
 487   @Override
 488   public void setName(String name)
 489   {
 490     this.name = name;
 491     this.parseId();
 492   }
 493
 494   /**
 495    * DOCUMENT ME!
 496    *
 497    * @return DOCUMENT ME!
 498    */
 499   @Override
 500   public String getName()
 501   {
 502     return this.name;
 503   }
 504
 505   /**
 506    * DOCUMENT ME!
 507    *
 508    * @param start
 509    *          DOCUMENT ME!
 510    */
 511   @Override
 512   public void setStart(int start)
 513   {
 514     this.start = start;
 515   }
 516
 517   /**
 518    * DOCUMENT ME!
 519    *
 520    * @return DOCUMENT ME!
 521    */
 522   @Override
 523   public int getStart()
 524   {
 525     return this.start;
 526   }
 527
 528   /**
 529    * DOCUMENT ME!
 530    *
 531    * @param end
 532    *          DOCUMENT ME!
 533    */
 534   @Override
 535   public void setEnd(int end)
 536   {
 537     this.end = end;
 538   }
 539
 540   /**
 541    * DOCUMENT ME!
 542    *
 543    * @return DOCUMENT ME!
 544    */
 545   @Override
 546   public int getEnd()
 547   {
 548     return this.end;
 549   }
 550
 551   /**
 552    * DOCUMENT ME!
 553    *
 554    * @return DOCUMENT ME!
 555    */
 556   @Override
 557   public int getLength()
 558   {
 559     return this.sequence.length;
 560   }
 561
 562   /**
 563    * DOCUMENT ME!
 564    *
 565    * @param seq
 566    *          DOCUMENT ME!
 567    */
 568   @Override
 569   public void setSequence(String seq)
 570   {
 571     this.sequence = seq.toCharArray();
 572     checkValidRange();
 573   }
 574
 575   @Override
 576   public String getSequenceAsString()
 577   {
 578     return new String(sequence);
 579   }
 580
 581   @Override
 582   public String getSequenceAsString(int start, int end)
 583   {
 584     return new String(getSequence(start, end));
 585   }
 586
 587   @Override
 588   public char[] getSequence()
 589   {
 590     return sequence;
 591   }
 592
 593   /*
 594    * (non-Javadoc)
 595    *
 596    * @see jalview.datamodel.SequenceI#getSequence(int, int)
 597    */
 598   @Override
 599   public char[] getSequence(int start, int end)
 600   {
 601     if (start < 0)
 602     {
 603       start = 0;
 604     }
 605     // JBPNote - left to user to pad the result here (TODO:Decide on this
 606     // policy)
 607     if (start >= sequence.length)
 608     {
 609       return new char[0];
 610     }
 611
 612     if (end >= sequence.length)
 613     {
 614       end = sequence.length;
 615     }
 616
 617     char[] reply = new char[end - start];
 618     System.arraycopy(sequence, start, reply, 0, end - start);
 619
 620     return reply;
 621   }
 622
 623   @Override
 624   public SequenceI getSubSequence(int start, int end)
 625   {
 626     if (start < 0)
 627     {
 628       start = 0;
 629     }
 630     char[] seq = getSequence(start, end);
 631     if (seq.length == 0)
 632     {
 633       return null;
 634     }
 635     int nstart = findPosition(start);
 636     int nend = findPosition(end) - 1;
 637     // JBPNote - this is an incomplete copy.
 638     SequenceI nseq = new Sequence(this.getName(), seq, nstart, nend);
 639     nseq.setDescription(description);
 640     if (datasetSequence != null)
 641     {
 642       nseq.setDatasetSequence(datasetSequence);
 643     }
 644     else
 645     {
 646       nseq.setDatasetSequence(this);
 647     }
 648     return nseq;
 649   }
 650
 651   /**
 652    * Returns the character of the aligned sequence at the given position (base
 653    * zero), or space if the position is not within the sequence's bounds
 654    *
 655    * @return
 656    */
 657   @Override
 658   public char getCharAt(int i)
 659   {
 660     if (i >= 0 && i < sequence.length)
 661     {
 662       return sequence[i];
 663     }
 664     else
 665     {
 666       return ' ';
 667     }
 668   }
 669
 670   /**
 671    * DOCUMENT ME!
 672    *
 673    * @param desc
 674    *          DOCUMENT ME!
 675    */
 676   @Override
 677   public void setDescription(String desc)
 678   {
 679     this.description = desc;
 680   }
 681
 682   /**
 683    * DOCUMENT ME!
 684    *
 685    * @return DOCUMENT ME!
 686    */
 687   @Override
 688   public String getDescription()
 689   {
 690     return this.description;
 691   }
 692
 693   /*
 694    * (non-Javadoc)
 695    *
 696    * @see jalview.datamodel.SequenceI#findIndex(int)
 697    */
 698   @Override
 699   public int findIndex(int pos)
 700   {
 701     // returns the alignment position for a residue
 702     int j = start;
 703     int i = 0;
 704     // Rely on end being at least as long as the length of the sequence.
 705     while ((i < sequence.length) && (j <= end) && (j <= pos))
 706     {
 707       if (!jalview.util.Comparison.isGap(sequence[i]))
 708       {
 709         j++;
 710       }
 711
 712       i++;
 713     }
 714
 715     if ((j == end) && (j < pos))
 716     {
 717       return end + 1;
 718     }
 719     else
 720     {
 721       return i;
 722     }
 723   }
 724
 725   @Override
 726   public int findPosition(int i)
 727   {
 728     int j = 0;
 729     int pos = start;
 730     int seqlen = sequence.length;
 731     while ((j < i) && (j < seqlen))
 732     {
 733       if (!jalview.util.Comparison.isGap(sequence[j]))
 734       {
 735         pos++;
 736       }
 737
 738       j++;
 739     }
 740
 741     return pos;
 742   }
 743
 744   /**
 745    * Returns an int array where indices correspond to each residue in the
 746    * sequence and the element value gives its position in the alignment
 747    *
 748    * @return int[SequenceI.getEnd()-SequenceI.getStart()+1] or null if no
 749    *         residues in SequenceI object
 750    */
 751   @Override
 752   public int[] gapMap()
 753   {
 754     String seq = jalview.analysis.AlignSeq.extractGaps(
 755             jalview.util.Comparison.GapChars, new String(sequence));
 756     int[] map = new int[seq.length()];
 757     int j = 0;
 758     int p = 0;
 759
 760     while (j < sequence.length)
 761     {
 762       if (!jalview.util.Comparison.isGap(sequence[j]))
 763       {
 764         map[p++] = j;
 765       }
 766
 767       j++;
 768     }
 769
 770     return map;
 771   }
 772
 773   @Override
 774   public int[] findPositionMap()
 775   {
 776     int map[] = new int[sequence.length];
 777     int j = 0;
 778     int pos = start;
 779     int seqlen = sequence.length;
 780     while ((j < seqlen))
 781     {
 782       map[j] = pos;
 783       if (!jalview.util.Comparison.isGap(sequence[j]))
 784       {
 785         pos++;
 786       }
 787
 788       j++;
 789     }
 790     return map;
 791   }
 792
 793   @Override
 794   public List<int[]> getInsertions()
 795   {
 796     ArrayList<int[]> map = new ArrayList<int[]>();
 797     int lastj = -1, j = 0;
 798     int pos = start;
 799     int seqlen = sequence.length;
 800     while ((j < seqlen))
 801     {
 802       if (jalview.util.Comparison.isGap(sequence[j]))
 803       {
 804         if (lastj == -1)
 805         {
 806           lastj = j;
 807         }
 808       }
 809       else
 810       {
 811         if (lastj != -1)
 812         {
 813           map.add(new int[] { lastj, j - 1 });
 814           lastj = -1;
 815         }
 816       }
 817       j++;
 818     }
 819     if (lastj != -1)
 820     {
 821       map.add(new int[] { lastj, j - 1 });
 822       lastj = -1;
 823     }
 824     return map;
 825   }
 826
 827   @Override
 828   public void deleteChars(int i, int j)
 829   {
 830     int newstart = start, newend = end;
 831     if (i >= sequence.length || i < 0)
 832     {
 833       return;
 834     }
 835
 836     char[] tmp = StringUtils.deleteChars(sequence, i, j);
 837     boolean createNewDs = false;
 838     // TODO: take a (second look) at the dataset creation validation method for
 839     // the very large sequence case
 840     int eindex = -1, sindex = -1;
 841     boolean ecalc = false, scalc = false;
 842     for (int s = i; s < j; s++)
 843     {
 844       if (jalview.schemes.ResidueProperties.aaIndex[sequence[s]] != 23)
 845       {
 846         if (createNewDs)
 847         {
 848           newend--;
 849         }
 850         else
 851         {
 852           if (!scalc)
 853           {
 854             sindex = findIndex(start) - 1;
 855             scalc = true;
 856           }
 857           if (sindex == s)
 858           {
 859             // delete characters including start of sequence
 860             newstart = findPosition(j);
 861             break; // don't need to search for any more residue characters.
 862           }
 863           else
 864           {
 865             // delete characters after start.
 866             if (!ecalc)
 867             {
 868               eindex = findIndex(end) - 1;
 869               ecalc = true;
 870             }
 871             if (eindex < j)
 872             {
 873               // delete characters at end of sequence
 874               newend = findPosition(i - 1);
 875               break; // don't need to search for any more residue characters.
 876             }
 877             else
 878             {
 879               createNewDs = true;
 880               newend--; // decrease end position by one for the deleted residue
 881               // and search further
 882             }
 883           }
 884         }
 885       }
 886     }
 887     // deletion occured in the middle of the sequence
 888     if (createNewDs && this.datasetSequence != null)
 889     {
 890       // construct a new sequence
 891       Sequence ds = new Sequence(datasetSequence);
 892       // TODO: remove any non-inheritable properties ?
 893       // TODO: create a sequence mapping (since there is a relation here ?)
 894       ds.deleteChars(i, j);
 895       datasetSequence = ds;
 896     }
 897     start = newstart;
 898     end = newend;
 899     sequence = tmp;
 900   }
 901
 902   @Override
 903   public void insertCharAt(int i, int length, char c)
 904   {
 905     char[] tmp = new char[sequence.length + length];
 906
 907     if (i >= sequence.length)
 908     {
 909       System.arraycopy(sequence, 0, tmp, 0, sequence.length);
 910       i = sequence.length;
 911     }
 912     else
 913     {
 914       System.arraycopy(sequence, 0, tmp, 0, i);
 915     }
 916
 917     int index = i;
 918     while (length > 0)
 919     {
 920       tmp[index++] = c;
 921       length--;
 922     }
 923
 924     if (i < sequence.length)
 925     {
 926       System.arraycopy(sequence, i, tmp, index, sequence.length - i);
 927     }
 928
 929     sequence = tmp;
 930   }
 931
 932   @Override
 933   public void insertCharAt(int i, char c)
 934   {
 935     insertCharAt(i, 1, c);
 936   }
 937
 938   @Override
 939   public String getVamsasId()
 940   {
 941     return vamsasId;
 942   }
 943
 944   @Override
 945   public void setVamsasId(String id)
 946   {
 947     vamsasId = id;
 948   }
 949
 950   @Override
 951   public void setDBRefs(DBRefEntry[] dbref)
 952   {
 953     if (dbrefs == null && datasetSequence != null
 954             && this != datasetSequence)
 955     {
 956       datasetSequence.setDBRefs(dbref);
 957       return;
 958     }
 959     dbrefs = dbref;
 960     if (dbrefs != null)
 961     {
 962       DBRefUtils.ensurePrimaries(this);
 963     }
 964   }
 965
 966   @Override
 967   public DBRefEntry[] getDBRefs()
 968   {
 969     if (dbrefs == null && datasetSequence != null
 970             && this != datasetSequence)
 971     {
 972       return datasetSequence.getDBRefs();
 973     }
 974     return dbrefs;
 975   }
 976
 977   @Override
 978   public void addDBRef(DBRefEntry entry)
 979   {
 980     if (datasetSequence != null)
 981     {
 982       datasetSequence.addDBRef(entry);
 983       return;
 984     }
 985
 986     if (dbrefs == null)
 987     {
 988       dbrefs = new DBRefEntry[0];
 989     }
 990
 991     for (DBRefEntryI dbr : dbrefs)
 992     {
 993       if (dbr.updateFrom(entry))
 994       {
 995         /*
 996          * found a dbref that either matched, or could be
 997          * updated from, the new entry - no need to add it
 998          */
 999         return;
1000       }
1001     }
1002
1003     /*
1004      * extend the array to make room for one more
1005      */
1006     // TODO use an ArrayList instead
1007     int j = dbrefs.length;
1008     DBRefEntry[] temp = new DBRefEntry[j + 1];
1009     System.arraycopy(dbrefs, 0, temp, 0, j);
1010     temp[temp.length - 1] = entry;
1011
1012     dbrefs = temp;
1013
1014     DBRefUtils.ensurePrimaries(this);
1015   }
1016
1017   @Override
1018   public void setDatasetSequence(SequenceI seq)
1019   {
1020     if (seq == this)
1021     {
1022       throw new IllegalArgumentException(
1023               "Implementation Error: self reference passed to SequenceI.setDatasetSequence");
1024     }
1025     if (seq != null && seq.getDatasetSequence() != null)
1026     {
1027       throw new IllegalArgumentException(
1028               "Implementation error: cascading dataset sequences are not allowed.");
1029     }
1030     datasetSequence = seq;
1031   }
1032
1033   @Override
1034   public SequenceI getDatasetSequence()
1035   {
1036     return datasetSequence;
1037   }
1038
1039   @Override
1040   public AlignmentAnnotation[] getAnnotation()
1041   {
1042     return annotation == null ? null : annotation
1043             .toArray(new AlignmentAnnotation[annotation.size()]);
1044   }
1045
1046   @Override
1047   public boolean hasAnnotation(AlignmentAnnotation ann)
1048   {
1049     return annotation == null ? false : annotation.contains(ann);
1050   }
1051
1052   @Override
1053   public void addAlignmentAnnotation(AlignmentAnnotation annotation)
1054   {
1055     if (this.annotation == null)
1056     {
1057       this.annotation = new Vector<AlignmentAnnotation>();
1058     }
1059     if (!this.annotation.contains(annotation))
1060     {
1061       this.annotation.addElement(annotation);
1062     }
1063     annotation.setSequenceRef(this);
1064   }
1065
1066   @Override
1067   public void removeAlignmentAnnotation(AlignmentAnnotation annotation)
1068   {
1069     if (this.annotation != null)
1070     {
1071       this.annotation.removeElement(annotation);
1072       if (this.annotation.size() == 0)
1073       {
1074         this.annotation = null;
1075       }
1076     }
1077   }
1078
1079   /**
1080    * test if this is a valid candidate for another sequence's dataset sequence.
1081    *
1082    */
1083   private boolean isValidDatasetSequence()
1084   {
1085     if (datasetSequence != null)
1086     {
1087       return false;
1088     }
1089     for (int i = 0; i < sequence.length; i++)
1090     {
1091       if (jalview.util.Comparison.isGap(sequence[i]))
1092       {
1093         return false;
1094       }
1095     }
1096     return true;
1097   }
1098
1099   @Override
1100   public SequenceI deriveSequence()
1101   {
1102     Sequence seq = null;
1103     if (datasetSequence == null)
1104     {
1105       if (isValidDatasetSequence())
1106       {
1107         // Use this as dataset sequence
1108         seq = new Sequence(getName(), "", 1, -1);
1109         seq.setDatasetSequence(this);
1110         seq.initSeqFrom(this, getAnnotation());
1111         return seq;
1112       }
1113       else
1114       {
1115         // Create a new, valid dataset sequence
1116         createDatasetSequence();
1117       }
1118     }
1119     return new Sequence(this);
1120   }
1121
1122   private boolean _isNa;
1123
1124   private long _seqhash = 0;
1125
1126   /**
1127    * Answers false if the sequence is more than 85% nucleotide (ACGTU), else
1128    * true
1129    */
1130   @Override
1131   public boolean isProtein()
1132   {
1133     if (datasetSequence != null)
1134     {
1135       return datasetSequence.isProtein();
1136     }
1137     if (_seqhash != sequence.hashCode())
1138     {
1139       _seqhash = sequence.hashCode();
1140       _isNa = Comparison.isNucleotide(this);
1141     }
1142     return !_isNa;
1143   };
1144
1145   /*
1146    * (non-Javadoc)
1147    *
1148    * @see jalview.datamodel.SequenceI#createDatasetSequence()
1149    */
1150   @Override
1151   public SequenceI createDatasetSequence()
1152   {
1153     if (datasetSequence == null)
1154     {
1155       Sequence dsseq = new Sequence(getName(), AlignSeq.extractGaps(
1156               jalview.util.Comparison.GapChars, getSequenceAsString()),
1157               getStart(), getEnd());
1158
1159       datasetSequence = dsseq;
1160
1161       dsseq.setDescription(description);
1162       // move features and database references onto dataset sequence
1163       dsseq.sequenceFeatures = sequenceFeatures;
1164       sequenceFeatures = null;
1165       dsseq.dbrefs = dbrefs;
1166       dbrefs = null;
1167       // TODO: search and replace any references to this sequence with
1168       // references to the dataset sequence in Mappings on dbref
1169       dsseq.pdbIds = pdbIds;
1170       pdbIds = null;
1171       datasetSequence.updatePDBIds();
1172       if (annotation != null)
1173       {
1174         // annotation is cloned rather than moved, to preserve what's currently
1175         // on the alignment
1176         for (AlignmentAnnotation aa : annotation)
1177         {
1178           AlignmentAnnotation _aa = new AlignmentAnnotation(aa);
1179           _aa.sequenceRef = datasetSequence;
1180           _aa.adjustForAlignment(); // uses annotation's own record of
1181                                     // sequence-column mapping
1182           datasetSequence.addAlignmentAnnotation(_aa);
1183         }
1184       }
1185     }
1186     return datasetSequence;
1187   }
1188
1189   /*
1190    * (non-Javadoc)
1191    *
1192    * @see
1193    * jalview.datamodel.SequenceI#setAlignmentAnnotation(AlignmmentAnnotation[]
1194    * annotations)
1195    */
1196   @Override
1197   public void setAlignmentAnnotation(AlignmentAnnotation[] annotations)
1198   {
1199     if (annotation != null)
1200     {
1201       annotation.removeAllElements();
1202     }
1203     if (annotations != null)
1204     {
1205       for (int i = 0; i < annotations.length; i++)
1206       {
1207         if (annotations[i] != null)
1208         {
1209           addAlignmentAnnotation(annotations[i]);
1210         }
1211       }
1212     }
1213   }
1214
1215   @Override
1216   public AlignmentAnnotation[] getAnnotation(String label)
1217   {
1218     if (annotation == null || annotation.size() == 0)
1219     {
1220       return null;
1221     }
1222
1223     Vector subset = new Vector();
1224     Enumeration e = annotation.elements();
1225     while (e.hasMoreElements())
1226     {
1227       AlignmentAnnotation ann = (AlignmentAnnotation) e.nextElement();
1228       if (ann.label != null && ann.label.equals(label))
1229       {
1230         subset.addElement(ann);
1231       }
1232     }
1233     if (subset.size() == 0)
1234     {
1235       return null;
1236     }
1237     AlignmentAnnotation[] anns = new AlignmentAnnotation[subset.size()];
1238     int i = 0;
1239     e = subset.elements();
1240     while (e.hasMoreElements())
1241     {
1242       anns[i++] = (AlignmentAnnotation) e.nextElement();
1243     }
1244     subset.removeAllElements();
1245     return anns;
1246   }
1247
1248   @Override
1249   public boolean updatePDBIds()
1250   {
1251     if (datasetSequence != null)
1252     {
1253       // TODO: could merge DBRefs
1254       return datasetSequence.updatePDBIds();
1255     }
1256     if (dbrefs == null || dbrefs.length == 0)
1257     {
1258       return false;
1259     }
1260     boolean added = false;
1261     for (DBRefEntry dbr : dbrefs)
1262     {
1263       if (DBRefSource.PDB.equals(dbr.getSource()))
1264       {
1265         /*
1266          * 'Add' any PDB dbrefs as a PDBEntry - add is only performed if the
1267          * PDB id is not already present in a 'matching' PDBEntry
1268          * Constructor parses out a chain code if appended to the accession id
1269          * (a fudge used to 'store' the chain code in the DBRef)
1270          */
1271         PDBEntry pdbe = new PDBEntry(dbr);
1272         added |= addPDBId(pdbe);
1273       }
1274     }
1275     return added;
1276   }
1277
1278   @Override
1279   public void transferAnnotation(SequenceI entry, Mapping mp)
1280   {
1281     if (datasetSequence != null)
1282     {
1283       datasetSequence.transferAnnotation(entry, mp);
1284       return;
1285     }
1286     if (entry.getDatasetSequence() != null)
1287     {
1288       transferAnnotation(entry.getDatasetSequence(), mp);
1289       return;
1290     }
1291     // transfer any new features from entry onto sequence
1292     if (entry.getSequenceFeatures() != null)
1293     {
1294
1295       SequenceFeature[] sfs = entry.getSequenceFeatures();
1296       for (int si = 0; si < sfs.length; si++)
1297       {
1298         SequenceFeature sf[] = (mp != null) ? mp.locateFeature(sfs[si])
1299                 : new SequenceFeature[] { new SequenceFeature(sfs[si]) };
1300         if (sf != null && sf.length > 0)
1301         {
1302           for (int sfi = 0; sfi < sf.length; sfi++)
1303           {
1304             addSequenceFeature(sf[sfi]);
1305           }
1306         }
1307       }
1308     }
1309
1310     // transfer PDB entries
1311     if (entry.getAllPDBEntries() != null)
1312     {
1313       Enumeration e = entry.getAllPDBEntries().elements();
1314       while (e.hasMoreElements())
1315       {
1316         PDBEntry pdb = (PDBEntry) e.nextElement();
1317         addPDBId(pdb);
1318       }
1319     }
1320     // transfer database references
1321     DBRefEntry[] entryRefs = entry.getDBRefs();
1322     if (entryRefs != null)
1323     {
1324       for (int r = 0; r < entryRefs.length; r++)
1325       {
1326         DBRefEntry newref = new DBRefEntry(entryRefs[r]);
1327         if (newref.getMap() != null && mp != null)
1328         {
1329           // remap ref using our local mapping
1330         }
1331         // we also assume all version string setting is done by dbSourceProxy
1332         /*
1333          * if (!newref.getSource().equalsIgnoreCase(dbSource)) {
1334          * newref.setSource(dbSource); }
1335          */
1336         addDBRef(newref);
1337       }
1338     }
1339   }
1340
1341   /**
1342    * @return The index (zero-based) on this sequence in the MSA. It returns
1343    *         {@code -1} if this information is not available.
1344    */
1345   @Override
1346   public int getIndex()
1347   {
1348     return index;
1349   }
1350
1351   /**
1352    * Defines the position of this sequence in the MSA. Use the value {@code -1}
1353    * if this information is undefined.
1354    *
1355    * @param The
1356    *          position for this sequence. This value is zero-based (zero for
1357    *          this first sequence)
1358    */
1359   @Override
1360   public void setIndex(int value)
1361   {
1362     index = value;
1363   }
1364
1365   @Override
1366   public void setRNA(RNA r)
1367   {
1368     rna = r;
1369   }
1370
1371   @Override
1372   public RNA getRNA()
1373   {
1374     return rna;
1375   }
1376
1377   @Override
1378   public List<AlignmentAnnotation> getAlignmentAnnotations(String calcId,
1379           String label)
1380   {
1381     List<AlignmentAnnotation> result = new ArrayList<AlignmentAnnotation>();
1382     if (this.annotation != null)
1383     {
1384       for (AlignmentAnnotation ann : annotation)
1385       {
1386         if (ann.calcId != null && ann.calcId.equals(calcId)
1387                 && ann.label != null && ann.label.equals(label))
1388         {
1389           result.add(ann);
1390         }
1391       }
1392     }
1393     return result;
1394   }
1395
1396   @Override
1397   public String toString()
1398   {
1399     return getDisplayId(false);
1400   }
1401
1402   @Override
1403   public PDBEntry getPDBEntry(String pdbIdStr)
1404   {
1405     if (getDatasetSequence() != null)
1406     {
1407       return getDatasetSequence().getPDBEntry(pdbIdStr);
1408     }
1409     if (pdbIds == null)
1410     {
1411       return null;
1412     }
1413     List<PDBEntry> entries = getAllPDBEntries();
1414     for (PDBEntry entry : entries)
1415     {
1416       if (entry.getId().equalsIgnoreCase(pdbIdStr))
1417       {
1418         return entry;
1419       }
1420     }
1421     return null;
1422   }
1423
1424   @Override
1425   public List<DBRefEntry> getPrimaryDBRefs()
1426   {
1427     if (datasetSequence != null)
1428     {
1429       return datasetSequence.getPrimaryDBRefs();
1430     }
1431     if (dbrefs == null || dbrefs.length == 0)
1432     {
1433       return Collections.emptyList();
1434     }
1435     synchronized (dbrefs)
1436     {
1437       List<DBRefEntry> primaries = new ArrayList<DBRefEntry>();
1438       DBRefEntry[] tmp = new DBRefEntry[1];
1439       for (DBRefEntry ref : dbrefs)
1440       {
1441         if (!ref.isPrimaryCandidate())
1442         {
1443           continue;
1444         }
1445         if (ref.hasMap())
1446         {
1447           MapList mp = ref.getMap().getMap();
1448           if (mp.getFromLowest() > start || mp.getFromHighest() < end)
1449           {
1450             // map only involves a subsequence, so cannot be primary
1451             continue;
1452           }
1453         }
1454         // whilst it looks like it is a primary ref, we also sanity check type
1455         if (DBRefUtils.getCanonicalName(DBRefSource.PDB).equals(
1456                 DBRefUtils.getCanonicalName(ref.getSource())))
1457         {
1458           // PDB dbrefs imply there should be a PDBEntry associated
1459           // TODO: tighten PDB dbrefs
1460           // formally imply Jalview has actually downloaded and
1461           // parsed the pdb file. That means there should be a cached file
1462           // handle on the PDBEntry, and a real mapping between sequence and
1463           // extracted sequence from PDB file
1464           PDBEntry pdbentry = getPDBEntry(ref.getAccessionId());
1465           if (pdbentry != null && pdbentry.getFile() != null)
1466           {
1467             primaries.add(ref);
1468           }
1469           continue;
1470         }
1471         // check standard protein or dna sources
1472         tmp[0] = ref;
1473         DBRefEntry[] res = DBRefUtils.selectDbRefs(!isProtein(), tmp);
1474         if (res != null && res[0] == tmp[0])
1475         {
1476           primaries.add(ref);
1477           continue;
1478         }
1479       }
1480       return primaries;
1481     }
1482   }
1483
1484   @Override
1485   public List<SequenceFeature> findFeatures(String type, int from, int to)
1486   {
1487     if (datasetSequence != null)
1488     {
1489       return datasetSequence.findFeatures(type, from, to);
1490     }
1491     return sequenceFeatureStore.findFeatures(type, from, to);
1492   }
1493 }