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.datamodel.features.SequenceFeaturesI;
  27 import jalview.util.Comparison;
  28 import jalview.util.DBRefUtils;
  29 import jalview.util.MapList;
  30 import jalview.util.StringUtils;
  31
  32 import java.util.ArrayList;
  33 import java.util.Arrays;
  34 import java.util.BitSet;
  35 import java.util.Collections;
  36 import java.util.Enumeration;
  37 import java.util.Iterator;
  38 import java.util.List;
  39 import java.util.ListIterator;
  40 import java.util.Vector;
  41
  42 import fr.orsay.lri.varna.models.rna.RNA;
  43
  44 /**
  45  *
  46  * Implements the SequenceI interface for a char[] based sequence object
  47  */
  48 public class Sequence extends ASequence implements SequenceI
  49 {
  50   SequenceI datasetSequence;
  51
  52   String name;
  53
  54   private char[] sequence;
  55
  56   String description;
  57
  58   int start;
  59
  60   int end;
  61
  62   Vector<PDBEntry> pdbIds;
  63
  64   String vamsasId;
  65
  66   DBRefEntry[] dbrefs;
  67
  68   RNA rna;
  69
  70   /**
  71    * This annotation is displayed below the alignment but the positions are tied
  72    * to the residues of this sequence
  73    *
  74    * TODO: change to List<>
  75    */
  76   Vector<AlignmentAnnotation> annotation;
  77
  78   private SequenceFeaturesI sequenceFeatureStore;
  79
  80   /*
  81    * A cursor holding the approximate current view position to the sequence,
  82    * as determined by findIndex or findPosition or findPositions.
  83    * Using a cursor as a hint allows these methods to be more performant for
  84    * large sequences.
  85    */
  86   private SequenceCursor cursor;
  87
  88   /*
  89    * A number that should be incremented whenever the sequence is edited.
  90    * If the value matches the cursor token, then we can trust the cursor,
  91    * if not then it should be recomputed.
  92    */
  93   private int changeCount;
  94
  95   /**
  96    * Creates a new Sequence object.
  97    *
  98    * @param name
  99    *          display name string
 100    * @param sequence
 101    *          string to form a possibly gapped sequence out of
 102    * @param start
 103    *          first position of non-gap residue in the sequence
 104    * @param end
 105    *          last position of ungapped residues (nearly always only used for
 106    *          display purposes)
 107    */
 108   public Sequence(String name, String sequence, int start, int end)
 109   {
 110     this();
 111     initSeqAndName(name, sequence.toCharArray(), start, end);
 112   }
 113
 114   public Sequence(String name, char[] sequence, int start, int end)
 115   {
 116     this();
 117     initSeqAndName(name, sequence, start, end);
 118   }
 119
 120   /**
 121    * Stage 1 constructor - assign name, sequence, and set start and end fields.
 122    * start and end are updated values from name2 if it ends with /start-end
 123    *
 124    * @param name2
 125    * @param sequence2
 126    * @param start2
 127    * @param end2
 128    */
 129   protected void initSeqAndName(String name2, char[] sequence2, int start2,
 130           int end2)
 131   {
 132     this.name = name2;
 133     this.sequence = sequence2;
 134     this.start = start2;
 135     this.end = end2;
 136     parseId();
 137     checkValidRange();
 138   }
 139
 140   /**
 141    * If 'name' ends in /i-j, where i >= j > 0 are integers, extracts i and j as
 142    * start and end respectively and removes the suffix from the name
 143    */
 144   void parseId()
 145   {
 146     if (name == null)
 147     {
 148       System.err.println(
 149               "POSSIBLE IMPLEMENTATION ERROR: null sequence name passed to constructor.");
 150       name = "";
 151     }
 152     int slashPos = name.lastIndexOf('/');
 153     if (slashPos > -1 && slashPos < name.length() - 1)
 154     {
 155       String suffix = name.substring(slashPos + 1);
 156       String[] range = suffix.split("-");
 157       if (range.length == 2)
 158       {
 159         try
 160         {
 161           int from = Integer.valueOf(range[0]);
 162           int to = Integer.valueOf(range[1]);
 163           if (from > 0 && to >= from)
 164           {
 165             name = name.substring(0, slashPos);
 166             setStart(from);
 167             setEnd(to);
 168             checkValidRange();
 169           }
 170         } catch (NumberFormatException e)
 171         {
 172           // leave name unchanged if suffix is invalid
 173         }
 174       }
 175     }
 176   }
 177
 178   /**
 179    * Ensures that 'end' is not before the end of the sequence, that is,
 180    * (end-start+1) is at least as long as the count of ungapped positions. Note
 181    * that end is permitted to be beyond the end of the sequence data.
 182    */
 183   void checkValidRange()
 184   {
 185     // Note: JAL-774 :
 186     // http://issues.jalview.org/browse/JAL-774?focusedCommentId=11239&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-11239
 187     {
 188       int endRes = 0;
 189       for (int j = 0; j < sequence.length; j++)
 190       {
 191         if (!Comparison.isGap(sequence[j]))
 192         {
 193           endRes++;
 194         }
 195       }
 196       if (endRes > 0)
 197       {
 198         endRes += start - 1;
 199       }
 200
 201       if (end < endRes)
 202       {
 203         end = endRes;
 204       }
 205     }
 206
 207   }
 208
 209   /**
 210    * default constructor
 211    */
 212   private Sequence()
 213   {
 214     sequenceFeatureStore = new SequenceFeatures();
 215   }
 216
 217   /**
 218    * Creates a new Sequence object.
 219    *
 220    * @param name
 221    *          DOCUMENT ME!
 222    * @param sequence
 223    *          DOCUMENT ME!
 224    */
 225   public Sequence(String name, String sequence)
 226   {
 227     this(name, sequence, 1, -1);
 228   }
 229
 230   /**
 231    * Creates a new Sequence object with new AlignmentAnnotations but inherits
 232    * any existing dataset sequence reference. If non exists, everything is
 233    * copied.
 234    *
 235    * @param seq
 236    *          if seq is a dataset sequence, behaves like a plain old copy
 237    *          constructor
 238    */
 239   public Sequence(SequenceI seq)
 240   {
 241     this(seq, seq.getAnnotation());
 242   }
 243
 244   /**
 245    * Create a new sequence object with new features, DBRefEntries, and PDBIds
 246    * but inherits any existing dataset sequence reference, and duplicate of any
 247    * annotation that is present in the given annotation array.
 248    *
 249    * @param seq
 250    *          the sequence to be copied
 251    * @param alAnnotation
 252    *          an array of annotation including some associated with seq
 253    */
 254   public Sequence(SequenceI seq, AlignmentAnnotation[] alAnnotation)
 255   {
 256     this();
 257     initSeqFrom(seq, alAnnotation);
 258   }
 259
 260   /**
 261    * does the heavy lifting when cloning a dataset sequence, or coping data from
 262    * dataset to a new derived sequence.
 263    *
 264    * @param seq
 265    *          - source of attributes.
 266    * @param alAnnotation
 267    *          - alignment annotation present on seq that should be copied onto
 268    *          this sequence
 269    */
 270   protected void initSeqFrom(SequenceI seq,
 271           AlignmentAnnotation[] alAnnotation)
 272   {
 273     char[] oseq = seq.getSequence(); // returns a copy of the array
 274     initSeqAndName(seq.getName(), oseq, seq.getStart(), seq.getEnd());
 275
 276     description = seq.getDescription();
 277     if (seq != datasetSequence)
 278     {
 279       setDatasetSequence(seq.getDatasetSequence());
 280     }
 281
 282     /*
 283      * only copy DBRefs and seqfeatures if we really are a dataset sequence
 284      */
 285     if (datasetSequence == null)
 286     {
 287       if (seq.getDBRefs() != null)
 288       {
 289         DBRefEntry[] dbr = seq.getDBRefs();
 290         for (int i = 0; i < dbr.length; i++)
 291         {
 292           addDBRef(new DBRefEntry(dbr[i]));
 293         }
 294       }
 295
 296       /*
 297        * make copies of any sequence features
 298        */
 299       for (SequenceFeature sf : seq.getSequenceFeatures())
 300       {
 301         addSequenceFeature(new SequenceFeature(sf));
 302       }
 303     }
 304
 305     if (seq.getAnnotation() != null)
 306     {
 307       AlignmentAnnotation[] sqann = seq.getAnnotation();
 308       for (int i = 0; i < sqann.length; i++)
 309       {
 310         if (sqann[i] == null)
 311         {
 312           continue;
 313         }
 314         boolean found = (alAnnotation == null);
 315         if (!found)
 316         {
 317           for (int apos = 0; !found && apos < alAnnotation.length; apos++)
 318           {
 319             found = (alAnnotation[apos] == sqann[i]);
 320           }
 321         }
 322         if (found)
 323         {
 324           // only copy the given annotation
 325           AlignmentAnnotation newann = new AlignmentAnnotation(sqann[i]);
 326           addAlignmentAnnotation(newann);
 327         }
 328       }
 329     }
 330     if (seq.getAllPDBEntries() != null)
 331     {
 332       Vector<PDBEntry> ids = seq.getAllPDBEntries();
 333       for (PDBEntry pdb : ids)
 334       {
 335         this.addPDBId(new PDBEntry(pdb));
 336       }
 337     }
 338   }
 339
 340   @Override
 341   public void setSequenceFeatures(List<SequenceFeature> features)
 342   {
 343     if (datasetSequence != null)
 344     {
 345       datasetSequence.setSequenceFeatures(features);
 346       return;
 347     }
 348     sequenceFeatureStore = new SequenceFeatures(features);
 349   }
 350
 351   @Override
 352   public synchronized boolean addSequenceFeature(SequenceFeature sf)
 353   {
 354     if (sf.getType() == null)
 355     {
 356       System.err.println("SequenceFeature type may not be null: "
 357               + sf.toString());
 358       return false;
 359     }
 360
 361     if (datasetSequence != null)
 362     {
 363       return datasetSequence.addSequenceFeature(sf);
 364     }
 365
 366     return sequenceFeatureStore.add(sf);
 367   }
 368
 369   @Override
 370   public void deleteFeature(SequenceFeature sf)
 371   {
 372     if (datasetSequence != null)
 373     {
 374       datasetSequence.deleteFeature(sf);
 375     }
 376     else
 377     {
 378       sequenceFeatureStore.delete(sf);
 379     }
 380   }
 381
 382   /**
 383    * {@inheritDoc}
 384    *
 385    * @return
 386    */
 387   @Override
 388   public List<SequenceFeature> getSequenceFeatures()
 389   {
 390     if (datasetSequence != null)
 391     {
 392       return datasetSequence.getSequenceFeatures();
 393     }
 394     return sequenceFeatureStore.getAllFeatures();
 395   }
 396
 397   @Override
 398   public SequenceFeaturesI getFeatures()
 399   {
 400     return datasetSequence != null ? datasetSequence.getFeatures()
 401             : sequenceFeatureStore;
 402   }
 403
 404   @Override
 405   public boolean addPDBId(PDBEntry entry)
 406   {
 407     if (pdbIds == null)
 408     {
 409       pdbIds = new Vector<>();
 410       pdbIds.add(entry);
 411       return true;
 412     }
 413
 414     for (PDBEntry pdbe : pdbIds)
 415     {
 416       if (pdbe.updateFrom(entry))
 417       {
 418         return false;
 419       }
 420     }
 421     pdbIds.addElement(entry);
 422     return true;
 423   }
 424
 425   /**
 426    * DOCUMENT ME!
 427    *
 428    * @param id
 429    *          DOCUMENT ME!
 430    */
 431   @Override
 432   public void setPDBId(Vector<PDBEntry> id)
 433   {
 434     pdbIds = id;
 435   }
 436
 437   /**
 438    * DOCUMENT ME!
 439    *
 440    * @return DOCUMENT ME!
 441    */
 442   @Override
 443   public Vector<PDBEntry> getAllPDBEntries()
 444   {
 445     return pdbIds == null ? new Vector<>() : pdbIds;
 446   }
 447
 448   /**
 449    * Answers the sequence name, with '/start-end' appended if jvsuffix is true
 450    *
 451    * @return
 452    */
 453   @Override
 454   public String getDisplayId(boolean jvsuffix)
 455   {
 456     if (!jvsuffix)
 457     {
 458       return name;
 459     }
 460     StringBuilder result = new StringBuilder(name);
 461     result.append("/").append(start).append("-").append(end);
 462
 463     return result.toString();
 464   }
 465
 466   /**
 467    * Sets the sequence name. If the name ends in /start-end, then the start-end
 468    * values are parsed out and set, and the suffix is removed from the name.
 469    *
 470    * @param theName
 471    */
 472   @Override
 473   public void setName(String theName)
 474   {
 475     this.name = theName;
 476     this.parseId();
 477   }
 478
 479   /**
 480    * DOCUMENT ME!
 481    *
 482    * @return DOCUMENT ME!
 483    */
 484   @Override
 485   public String getName()
 486   {
 487     return this.name;
 488   }
 489
 490   /**
 491    * DOCUMENT ME!
 492    *
 493    * @param start
 494    *          DOCUMENT ME!
 495    */
 496   @Override
 497   public void setStart(int start)
 498   {
 499     this.start = start;
 500     sequenceChanged();
 501   }
 502
 503   /**
 504    * DOCUMENT ME!
 505    *
 506    * @return DOCUMENT ME!
 507    */
 508   @Override
 509   public int getStart()
 510   {
 511     return this.start;
 512   }
 513
 514   /**
 515    * DOCUMENT ME!
 516    *
 517    * @param end
 518    *          DOCUMENT ME!
 519    */
 520   @Override
 521   public void setEnd(int end)
 522   {
 523     this.end = end;
 524   }
 525
 526   /**
 527    * DOCUMENT ME!
 528    *
 529    * @return DOCUMENT ME!
 530    */
 531   @Override
 532   public int getEnd()
 533   {
 534     return this.end;
 535   }
 536
 537   /**
 538    * DOCUMENT ME!
 539    *
 540    * @return DOCUMENT ME!
 541    */
 542   @Override
 543   public int getLength()
 544   {
 545     return this.sequence.length;
 546   }
 547
 548   /**
 549    * DOCUMENT ME!
 550    *
 551    * @param seq
 552    *          DOCUMENT ME!
 553    */
 554   @Override
 555   public void setSequence(String seq)
 556   {
 557     this.sequence = seq.toCharArray();
 558     checkValidRange();
 559     sequenceChanged();
 560   }
 561
 562   @Override
 563   public String getSequenceAsString()
 564   {
 565     return new String(sequence);
 566   }
 567
 568   @Override
 569   public String getSequenceAsString(int start, int end)
 570   {
 571     return new String(getSequence(start, end));
 572   }
 573
 574   @Override
 575   public char[] getSequence()
 576   {
 577     // return sequence;
 578     return sequence == null ? null : Arrays.copyOf(sequence,
 579             sequence.length);
 580   }
 581
 582   /*
 583    * (non-Javadoc)
 584    *
 585    * @see jalview.datamodel.SequenceI#getSequence(int, int)
 586    */
 587   @Override
 588   public char[] getSequence(int start, int end)
 589   {
 590     if (start < 0)
 591     {
 592       start = 0;
 593     }
 594     // JBPNote - left to user to pad the result here (TODO:Decide on this
 595     // policy)
 596     if (start >= sequence.length)
 597     {
 598       return new char[0];
 599     }
 600
 601     if (end >= sequence.length)
 602     {
 603       end = sequence.length;
 604     }
 605
 606     char[] reply = new char[end - start];
 607     System.arraycopy(sequence, start, reply, 0, end - start);
 608
 609     return reply;
 610   }
 611
 612   @Override
 613   public SequenceI getSubSequence(int start, int end)
 614   {
 615     if (start < 0)
 616     {
 617       start = 0;
 618     }
 619     char[] seq = getSequence(start, end);
 620     if (seq.length == 0)
 621     {
 622       return null;
 623     }
 624     int nstart = findPosition(start);
 625     int nend = findPosition(end) - 1;
 626     // JBPNote - this is an incomplete copy.
 627     SequenceI nseq = new Sequence(this.getName(), seq, nstart, nend);
 628     nseq.setDescription(description);
 629     if (datasetSequence != null)
 630     {
 631       nseq.setDatasetSequence(datasetSequence);
 632     }
 633     else
 634     {
 635       nseq.setDatasetSequence(this);
 636     }
 637     return nseq;
 638   }
 639
 640   /**
 641    * Returns the character of the aligned sequence at the given position (base
 642    * zero), or space if the position is not within the sequence's bounds
 643    *
 644    * @return
 645    */
 646   @Override
 647   public char getCharAt(int i)
 648   {
 649     if (i >= 0 && i < sequence.length)
 650     {
 651       return sequence[i];
 652     }
 653     else
 654     {
 655       return ' ';
 656     }
 657   }
 658
 659   /**
 660    * Sets the sequence description, and also parses out any special formats of
 661    * interest
 662    *
 663    * @param desc
 664    */
 665   @Override
 666   public void setDescription(String desc)
 667   {
 668     this.description = desc;
 669   }
 670
 671   @Override
 672   public void setGeneLoci(String speciesId, String assemblyId,
 673           String chromosomeId, MapList map)
 674   {
 675     addDBRef(new GeneLocus(speciesId, assemblyId, chromosomeId,
 676             new Mapping(map)));
 677   }
 678
 679   /**
 680    * Returns the gene loci mapping for the sequence (may be null)
 681    *
 682    * @return
 683    */
 684   @Override
 685   public GeneLociI getGeneLoci()
 686   {
 687     DBRefEntry[] refs = getDBRefs();
 688     if (refs != null)
 689     {
 690       for (final DBRefEntry ref : refs)
 691       {
 692         if (ref instanceof GeneLociI)
 693         {
 694           return (GeneLociI) ref;
 695         }
 696       }
 697     }
 698     return null;
 699   }
 700
 701   /**
 702    * Answers the description
 703    *
 704    * @return
 705    */
 706   @Override
 707   public String getDescription()
 708   {
 709     return this.description;
 710   }
 711
 712   /**
 713    * {@inheritDoc}
 714    */
 715   @Override
 716   public int findIndex(int pos)
 717   {
 718     /*
 719      * use a valid, hopefully nearby, cursor if available
 720      */
 721     if (isValidCursor(cursor))
 722     {
 723       return findIndex(pos, cursor);
 724     }
 725
 726     int j = start;
 727     int i = 0;
 728     int startColumn = 0;
 729
 730     /*
 731      * traverse sequence from the start counting gaps; make a note of
 732      * the column of the first residue to save in the cursor
 733      */
 734     while ((i < sequence.length) && (j <= end) && (j <= pos))
 735     {
 736       if (!Comparison.isGap(sequence[i]))
 737       {
 738         if (j == start)
 739         {
 740           startColumn = i;
 741         }
 742         j++;
 743       }
 744       i++;
 745     }
 746
 747     if (j == end && j < pos)
 748     {
 749       return end + 1;
 750     }
 751
 752     updateCursor(pos, i, startColumn);
 753     return i;
 754   }
 755
 756   /**
 757    * Updates the cursor to the latest found residue and column position
 758    *
 759    * @param residuePos
 760    *          (start..)
 761    * @param column
 762    *          (1..)
 763    * @param startColumn
 764    *          column position of the first sequence residue
 765    */
 766   protected void updateCursor(int residuePos, int column, int startColumn)
 767   {
 768     /*
 769      * preserve end residue column provided cursor was valid
 770      */
 771     int endColumn = isValidCursor(cursor) ? cursor.lastColumnPosition : 0;
 772
 773     if (residuePos == this.end)
 774     {
 775       endColumn = column;
 776     }
 777
 778     cursor = new SequenceCursor(this, residuePos, column, startColumn,
 779             endColumn, this.changeCount);
 780   }
 781
 782   /**
 783    * Answers the aligned column position (1..) for the given residue position
 784    * (start..) given a 'hint' of a residue/column location in the neighbourhood.
 785    * The hint may be left of, at, or to the right of the required position.
 786    *
 787    * @param pos
 788    * @param curs
 789    * @return
 790    */
 791   protected int findIndex(final int pos, SequenceCursor curs)
 792   {
 793     if (!isValidCursor(curs))
 794     {
 795       /*
 796        * wrong or invalidated cursor, compute de novo
 797        */
 798       return findIndex(pos);
 799     }
 800
 801     if (curs.residuePosition == pos)
 802     {
 803       return curs.columnPosition;
 804     }
 805
 806     /*
 807      * move left or right to find pos from hint.position
 808      */
 809     int col = curs.columnPosition - 1; // convert from base 1 to base 0
 810     int newPos = curs.residuePosition;
 811     int delta = newPos > pos ? -1 : 1;
 812
 813     while (newPos != pos)
 814     {
 815       col += delta; // shift one column left or right
 816       if (col < 0)
 817       {
 818         break;
 819       }
 820       if (col == sequence.length)
 821       {
 822         col--; // return last column if we failed to reach pos
 823         break;
 824       }
 825       if (!Comparison.isGap(sequence[col]))
 826       {
 827         newPos += delta;
 828       }
 829     }
 830
 831     col++; // convert back to base 1
 832
 833     /*
 834      * only update cursor if we found the target position
 835      */
 836     if (newPos == pos)
 837     {
 838       updateCursor(pos, col, curs.firstColumnPosition);
 839     }
 840
 841     return col;
 842   }
 843
 844   /**
 845    * {@inheritDoc}
 846    */
 847   @Override
 848   public int findPosition(final int column)
 849   {
 850     /*
 851      * use a valid, hopefully nearby, cursor if available
 852      */
 853     if (isValidCursor(cursor))
 854     {
 855       return findPosition(column + 1, cursor);
 856     }
 857
 858     // TODO recode this more naturally i.e. count residues only
 859     // as they are found, not 'in anticipation'
 860
 861     /*
 862      * traverse the sequence counting gaps; note the column position
 863      * of the first residue, to save in the cursor
 864      */
 865     int firstResidueColumn = 0;
 866     int lastPosFound = 0;
 867     int lastPosFoundColumn = 0;
 868     int seqlen = sequence.length;
 869
 870     if (seqlen > 0 && !Comparison.isGap(sequence[0]))
 871     {
 872       lastPosFound = start;
 873       lastPosFoundColumn = 0;
 874     }
 875
 876     int j = 0;
 877     int pos = start;
 878
 879     while (j < column && j < seqlen)
 880     {
 881       if (!Comparison.isGap(sequence[j]))
 882       {
 883         lastPosFound = pos;
 884         lastPosFoundColumn = j;
 885         if (pos == this.start)
 886         {
 887           firstResidueColumn = j;
 888         }
 889         pos++;
 890       }
 891       j++;
 892     }
 893     if (j < seqlen && !Comparison.isGap(sequence[j]))
 894     {
 895       lastPosFound = pos;
 896       lastPosFoundColumn = j;
 897       if (pos == this.start)
 898       {
 899         firstResidueColumn = j;
 900       }
 901     }
 902
 903     /*
 904      * update the cursor to the last residue position found (if any)
 905      * (converting column position to base 1)
 906      */
 907     if (lastPosFound != 0)
 908     {
 909       updateCursor(lastPosFound, lastPosFoundColumn + 1,
 910               firstResidueColumn + 1);
 911     }
 912
 913     return pos;
 914   }
 915
 916   /**
 917    * Answers true if the given cursor is not null, is for this sequence object,
 918    * and has a token value that matches this object's changeCount, else false.
 919    * This allows us to ignore a cursor as 'stale' if the sequence has been
 920    * modified since the cursor was created.
 921    *
 922    * @param curs
 923    * @return
 924    */
 925   protected boolean isValidCursor(SequenceCursor curs)
 926   {
 927     if (curs == null || curs.sequence != this || curs.token != changeCount)
 928     {
 929       return false;
 930     }
 931     /*
 932      * sanity check against range
 933      */
 934     if (curs.columnPosition < 0 || curs.columnPosition > sequence.length)
 935     {
 936       return false;
 937     }
 938     if (curs.residuePosition < start || curs.residuePosition > end)
 939     {
 940       return false;
 941     }
 942     return true;
 943   }
 944
 945   /**
 946    * Answers the sequence position (start..) for the given aligned column
 947    * position (1..), given a hint of a cursor in the neighbourhood. The cursor
 948    * may lie left of, at, or to the right of the column position.
 949    *
 950    * @param col
 951    * @param curs
 952    * @return
 953    */
 954   protected int findPosition(final int col, SequenceCursor curs)
 955   {
 956     if (!isValidCursor(curs))
 957     {
 958       /*
 959        * wrong or invalidated cursor, compute de novo
 960        */
 961       return findPosition(col - 1);// ugh back to base 0
 962     }
 963
 964     if (curs.columnPosition == col)
 965     {
 966       cursor = curs; // in case this method becomes public
 967       return curs.residuePosition; // easy case :-)
 968     }
 969
 970     if (curs.lastColumnPosition > 0 && curs.lastColumnPosition < col)
 971     {
 972       /*
 973        * sequence lies entirely to the left of col
 974        * - return last residue + 1
 975        */
 976       return end + 1;
 977     }
 978
 979     if (curs.firstColumnPosition > 0 && curs.firstColumnPosition > col)
 980     {
 981       /*
 982        * sequence lies entirely to the right of col
 983        * - return first residue
 984        */
 985       return start;
 986     }
 987
 988     // todo could choose closest to col out of column,
 989     // firstColumnPosition, lastColumnPosition as a start point
 990
 991     /*
 992      * move left or right to find pos from cursor position
 993      */
 994     int firstResidueColumn = curs.firstColumnPosition;
 995     int column = curs.columnPosition - 1; // to base 0
 996     int newPos = curs.residuePosition;
 997     int delta = curs.columnPosition > col ? -1 : 1;
 998     boolean gapped = false;
 999     int lastFoundPosition = curs.residuePosition;
1000     int lastFoundPositionColumn = curs.columnPosition;
1001
1002     while (column != col - 1)
1003     {
1004       column += delta; // shift one column left or right
1005       if (column < 0 || column == sequence.length)
1006       {
1007         break;
1008       }
1009       gapped = Comparison.isGap(sequence[column]);
1010       if (!gapped)
1011       {
1012         newPos += delta;
1013         lastFoundPosition = newPos;
1014         lastFoundPositionColumn = column + 1;
1015         if (lastFoundPosition == this.start)
1016         {
1017           firstResidueColumn = column + 1;
1018         }
1019       }
1020     }
1021
1022     if (cursor == null || lastFoundPosition != cursor.residuePosition)
1023     {
1024       updateCursor(lastFoundPosition, lastFoundPositionColumn,
1025               firstResidueColumn);
1026     }
1027
1028     /*
1029      * hack to give position to the right if on a gap
1030      * or beyond the length of the sequence (see JAL-2562)
1031      */
1032     if (delta > 0 && (gapped || column >= sequence.length))
1033     {
1034       newPos++;
1035     }
1036
1037     return newPos;
1038   }
1039
1040   /**
1041    * {@inheritDoc}
1042    */
1043   @Override
1044   public ContiguousI findPositions(int fromColumn, int toColumn)
1045   {
1046     if (toColumn < fromColumn || fromColumn < 1)
1047     {
1048       return null;
1049     }
1050
1051     /*
1052      * find the first non-gapped position, if any
1053      */
1054     int firstPosition = 0;
1055     int col = fromColumn - 1;
1056     int length = sequence.length;
1057     while (col < length && col < toColumn)
1058     {
1059       if (!Comparison.isGap(sequence[col]))
1060       {
1061         firstPosition = findPosition(col++);
1062         break;
1063       }
1064       col++;
1065     }
1066
1067     if (firstPosition == 0)
1068     {
1069       return null;
1070     }
1071
1072     /*
1073      * find the last non-gapped position
1074      */
1075     int lastPosition = firstPosition;
1076     while (col < length && col < toColumn)
1077     {
1078       if (!Comparison.isGap(sequence[col++]))
1079       {
1080         lastPosition++;
1081       }
1082     }
1083
1084     return new Range(firstPosition, lastPosition);
1085   }
1086
1087   /**
1088    * Returns an int array where indices correspond to each residue in the
1089    * sequence and the element value gives its position in the alignment
1090    *
1091    * @return int[SequenceI.getEnd()-SequenceI.getStart()+1] or null if no
1092    *         residues in SequenceI object
1093    */
1094   @Override
1095   public int[] gapMap()
1096   {
1097     String seq = jalview.analysis.AlignSeq.extractGaps(
1098             jalview.util.Comparison.GapChars, new String(sequence));
1099     int[] map = new int[seq.length()];
1100     int j = 0;
1101     int p = 0;
1102
1103     while (j < sequence.length)
1104     {
1105       if (!jalview.util.Comparison.isGap(sequence[j]))
1106       {
1107         map[p++] = j;
1108       }
1109
1110       j++;
1111     }
1112
1113     return map;
1114   }
1115
1116   /**
1117    * Build a bitset corresponding to sequence gaps
1118    *
1119    * @return a BitSet where set values correspond to gaps in the sequence
1120    */
1121   @Override
1122   public BitSet gapBitset()
1123   {
1124     BitSet gaps = new BitSet(sequence.length);
1125     int j = 0;
1126     while (j < sequence.length)
1127     {
1128       if (jalview.util.Comparison.isGap(sequence[j]))
1129       {
1130         gaps.set(j);
1131       }
1132       j++;
1133     }
1134     return gaps;
1135   }
1136
1137   @Override
1138   public int[] findPositionMap()
1139   {
1140     int map[] = new int[sequence.length];
1141     int j = 0;
1142     int pos = start;
1143     int seqlen = sequence.length;
1144     while ((j < seqlen))
1145     {
1146       map[j] = pos;
1147       if (!jalview.util.Comparison.isGap(sequence[j]))
1148       {
1149         pos++;
1150       }
1151
1152       j++;
1153     }
1154     return map;
1155   }
1156
1157   @Override
1158   public List<int[]> getInsertions()
1159   {
1160     ArrayList<int[]> map = new ArrayList<>();
1161     int lastj = -1, j = 0;
1162     int pos = start;
1163     int seqlen = sequence.length;
1164     while ((j < seqlen))
1165     {
1166       if (jalview.util.Comparison.isGap(sequence[j]))
1167       {
1168         if (lastj == -1)
1169         {
1170           lastj = j;
1171         }
1172       }
1173       else
1174       {
1175         if (lastj != -1)
1176         {
1177           map.add(new int[] { lastj, j - 1 });
1178           lastj = -1;
1179         }
1180       }
1181       j++;
1182     }
1183     if (lastj != -1)
1184     {
1185       map.add(new int[] { lastj, j - 1 });
1186       lastj = -1;
1187     }
1188     return map;
1189   }
1190
1191   @Override
1192   public BitSet getInsertionsAsBits()
1193   {
1194     BitSet map = new BitSet();
1195     int lastj = -1, j = 0;
1196     int pos = start;
1197     int seqlen = sequence.length;
1198     while ((j < seqlen))
1199     {
1200       if (jalview.util.Comparison.isGap(sequence[j]))
1201       {
1202         if (lastj == -1)
1203         {
1204           lastj = j;
1205         }
1206       }
1207       else
1208       {
1209         if (lastj != -1)
1210         {
1211           map.set(lastj, j);
1212           lastj = -1;
1213         }
1214       }
1215       j++;
1216     }
1217     if (lastj != -1)
1218     {
1219       map.set(lastj, j);
1220       lastj = -1;
1221     }
1222     return map;
1223   }
1224
1225   @Override
1226   public void deleteChars(final int i, final int j)
1227   {
1228     int newstart = start, newend = end;
1229     if (i >= sequence.length || i < 0)
1230     {
1231       return;
1232     }
1233
1234     char[] tmp = StringUtils.deleteChars(sequence, i, j);
1235     boolean createNewDs = false;
1236     // TODO: take a (second look) at the dataset creation validation method for
1237     // the very large sequence case
1238
1239     int startIndex = findIndex(start) - 1;
1240     int endIndex = findIndex(end) - 1;
1241     int startDeleteColumn = -1; // for dataset sequence deletions
1242     int deleteCount = 0;
1243
1244     for (int s = i; s < j && s < sequence.length; s++)
1245     {
1246       if (Comparison.isGap(sequence[s]))
1247       {
1248         continue;
1249       }
1250       deleteCount++;
1251       if (startDeleteColumn == -1)
1252       {
1253         startDeleteColumn = findPosition(s) - start;
1254       }
1255       if (createNewDs)
1256       {
1257         newend--;
1258       }
1259       else
1260       {
1261         if (startIndex == s)
1262         {
1263           /*
1264            * deleting characters from start of sequence; new start is the
1265            * sequence position of the next column (position to the right
1266            * if the column position is gapped)
1267            */
1268           newstart = findPosition(j);
1269           break;
1270         }
1271         else
1272         {
1273           if (endIndex < j)
1274           {
1275             /*
1276              * deleting characters at end of sequence; new end is the sequence
1277              * position of the column before the deletion; subtract 1 if this is
1278              * gapped since findPosition returns the next sequence position
1279              */
1280             newend = findPosition(i - 1);
1281             if (Comparison.isGap(sequence[i - 1]))
1282             {
1283               newend--;
1284             }
1285             break;
1286           }
1287           else
1288           {
1289             createNewDs = true;
1290             newend--;
1291           }
1292         }
1293       }
1294     }
1295
1296     if (createNewDs && this.datasetSequence != null)
1297     {
1298       /*
1299        * if deletion occured in the middle of the sequence,
1300        * construct a new dataset sequence and delete the residues
1301        * that were deleted from the aligned sequence
1302        */
1303       Sequence ds = new Sequence(datasetSequence);
1304       ds.deleteChars(startDeleteColumn, startDeleteColumn + deleteCount);
1305       datasetSequence = ds;
1306       // TODO: remove any non-inheritable properties ?
1307       // TODO: create a sequence mapping (since there is a relation here ?)
1308     }
1309     start = newstart;
1310     end = newend;
1311     sequence = tmp;
1312     sequenceChanged();
1313   }
1314
1315   @Override
1316   public void insertCharAt(int i, int length, char c)
1317   {
1318     char[] tmp = new char[sequence.length + length];
1319
1320     if (i >= sequence.length)
1321     {
1322       System.arraycopy(sequence, 0, tmp, 0, sequence.length);
1323       i = sequence.length;
1324     }
1325     else
1326     {
1327       System.arraycopy(sequence, 0, tmp, 0, i);
1328     }
1329
1330     int index = i;
1331     while (length > 0)
1332     {
1333       tmp[index++] = c;
1334       length--;
1335     }
1336
1337     if (i < sequence.length)
1338     {
1339       System.arraycopy(sequence, i, tmp, index, sequence.length - i);
1340     }
1341
1342     sequence = tmp;
1343     sequenceChanged();
1344   }
1345
1346   @Override
1347   public void insertCharAt(int i, char c)
1348   {
1349     insertCharAt(i, 1, c);
1350   }
1351
1352   @Override
1353   public String getVamsasId()
1354   {
1355     return vamsasId;
1356   }
1357
1358   @Override
1359   public void setVamsasId(String id)
1360   {
1361     vamsasId = id;
1362   }
1363
1364   @Override
1365   public void setDBRefs(DBRefEntry[] dbref)
1366   {
1367     if (dbrefs == null && datasetSequence != null
1368             && this != datasetSequence)
1369     {
1370       datasetSequence.setDBRefs(dbref);
1371       return;
1372     }
1373     dbrefs = dbref;
1374     if (dbrefs != null)
1375     {
1376       DBRefUtils.ensurePrimaries(this);
1377     }
1378   }
1379
1380   @Override
1381   public DBRefEntry[] getDBRefs()
1382   {
1383     if (dbrefs == null && datasetSequence != null
1384             && this != datasetSequence)
1385     {
1386       return datasetSequence.getDBRefs();
1387     }
1388     return dbrefs;
1389   }
1390
1391   @Override
1392   public void addDBRef(DBRefEntry entry)
1393   {
1394     if (datasetSequence != null)
1395     {
1396       datasetSequence.addDBRef(entry);
1397       return;
1398     }
1399
1400     if (dbrefs == null)
1401     {
1402       dbrefs = new DBRefEntry[0];
1403     }
1404
1405     for (DBRefEntryI dbr : dbrefs)
1406     {
1407       if (dbr.updateFrom(entry))
1408       {
1409         /*
1410          * found a dbref that either matched, or could be
1411          * updated from, the new entry - no need to add it
1412          */
1413         return;
1414       }
1415     }
1416
1417     /*
1418      * extend the array to make room for one more
1419      */
1420     // TODO use an ArrayList instead
1421     int j = dbrefs.length;
1422     DBRefEntry[] temp = new DBRefEntry[j + 1];
1423     System.arraycopy(dbrefs, 0, temp, 0, j);
1424     temp[temp.length - 1] = entry;
1425
1426     dbrefs = temp;
1427
1428     DBRefUtils.ensurePrimaries(this);
1429   }
1430
1431   @Override
1432   public void setDatasetSequence(SequenceI seq)
1433   {
1434     if (seq == this)
1435     {
1436       throw new IllegalArgumentException(
1437               "Implementation Error: self reference passed to SequenceI.setDatasetSequence");
1438     }
1439     if (seq != null && seq.getDatasetSequence() != null)
1440     {
1441       throw new IllegalArgumentException(
1442               "Implementation error: cascading dataset sequences are not allowed.");
1443     }
1444     datasetSequence = seq;
1445   }
1446
1447   @Override
1448   public SequenceI getDatasetSequence()
1449   {
1450     return datasetSequence;
1451   }
1452
1453   @Override
1454   public AlignmentAnnotation[] getAnnotation()
1455   {
1456     return annotation == null ? null
1457             : annotation
1458                     .toArray(new AlignmentAnnotation[annotation.size()]);
1459   }
1460
1461   @Override
1462   public boolean hasAnnotation(AlignmentAnnotation ann)
1463   {
1464     return annotation == null ? false : annotation.contains(ann);
1465   }
1466
1467   @Override
1468   public void addAlignmentAnnotation(AlignmentAnnotation annotation)
1469   {
1470     if (this.annotation == null)
1471     {
1472       this.annotation = new Vector<>();
1473     }
1474     if (!this.annotation.contains(annotation))
1475     {
1476       this.annotation.addElement(annotation);
1477     }
1478     annotation.setSequenceRef(this);
1479   }
1480
1481   @Override
1482   public void removeAlignmentAnnotation(AlignmentAnnotation annotation)
1483   {
1484     if (this.annotation != null)
1485     {
1486       this.annotation.removeElement(annotation);
1487       if (this.annotation.size() == 0)
1488       {
1489         this.annotation = null;
1490       }
1491     }
1492   }
1493
1494   /**
1495    * test if this is a valid candidate for another sequence's dataset sequence.
1496    *
1497    */
1498   private boolean isValidDatasetSequence()
1499   {
1500     if (datasetSequence != null)
1501     {
1502       return false;
1503     }
1504     for (int i = 0; i < sequence.length; i++)
1505     {
1506       if (jalview.util.Comparison.isGap(sequence[i]))
1507       {
1508         return false;
1509       }
1510     }
1511     return true;
1512   }
1513
1514   @Override
1515   public SequenceI deriveSequence()
1516   {
1517     Sequence seq = null;
1518     if (datasetSequence == null)
1519     {
1520       if (isValidDatasetSequence())
1521       {
1522         // Use this as dataset sequence
1523         seq = new Sequence(getName(), "", 1, -1);
1524         seq.setDatasetSequence(this);
1525         seq.initSeqFrom(this, getAnnotation());
1526         return seq;
1527       }
1528       else
1529       {
1530         // Create a new, valid dataset sequence
1531         createDatasetSequence();
1532       }
1533     }
1534     return new Sequence(this);
1535   }
1536
1537   private boolean _isNa;
1538
1539   private int _seqhash = 0;
1540
1541   /**
1542    * Answers false if the sequence is more than 85% nucleotide (ACGTU), else
1543    * true
1544    */
1545   @Override
1546   public boolean isProtein()
1547   {
1548     if (datasetSequence != null)
1549     {
1550       return datasetSequence.isProtein();
1551     }
1552     if (_seqhash != sequence.hashCode())
1553     {
1554       _seqhash = sequence.hashCode();
1555       _isNa = Comparison.isNucleotide(this);
1556     }
1557     return !_isNa;
1558   };
1559
1560   /*
1561    * (non-Javadoc)
1562    *
1563    * @see jalview.datamodel.SequenceI#createDatasetSequence()
1564    */
1565   @Override
1566   public SequenceI createDatasetSequence()
1567   {
1568     if (datasetSequence == null)
1569     {
1570       Sequence dsseq = new Sequence(getName(),
1571               AlignSeq.extractGaps(jalview.util.Comparison.GapChars,
1572                       getSequenceAsString()),
1573               getStart(), getEnd());
1574
1575       datasetSequence = dsseq;
1576
1577       dsseq.setDescription(description);
1578       // move features and database references onto dataset sequence
1579       dsseq.sequenceFeatureStore = sequenceFeatureStore;
1580       sequenceFeatureStore = null;
1581       dsseq.dbrefs = dbrefs;
1582       dbrefs = null;
1583       // TODO: search and replace any references to this sequence with
1584       // references to the dataset sequence in Mappings on dbref
1585       dsseq.pdbIds = pdbIds;
1586       pdbIds = null;
1587       datasetSequence.updatePDBIds();
1588       if (annotation != null)
1589       {
1590         // annotation is cloned rather than moved, to preserve what's currently
1591         // on the alignment
1592         for (AlignmentAnnotation aa : annotation)
1593         {
1594           AlignmentAnnotation _aa = new AlignmentAnnotation(aa);
1595           _aa.sequenceRef = datasetSequence;
1596           _aa.adjustForAlignment(); // uses annotation's own record of
1597                                     // sequence-column mapping
1598           datasetSequence.addAlignmentAnnotation(_aa);
1599         }
1600       }
1601     }
1602     return datasetSequence;
1603   }
1604
1605   /*
1606    * (non-Javadoc)
1607    *
1608    * @see
1609    * jalview.datamodel.SequenceI#setAlignmentAnnotation(AlignmmentAnnotation[]
1610    * annotations)
1611    */
1612   @Override
1613   public void setAlignmentAnnotation(AlignmentAnnotation[] annotations)
1614   {
1615     if (annotation != null)
1616     {
1617       annotation.removeAllElements();
1618     }
1619     if (annotations != null)
1620     {
1621       for (int i = 0; i < annotations.length; i++)
1622       {
1623         if (annotations[i] != null)
1624         {
1625           addAlignmentAnnotation(annotations[i]);
1626         }
1627       }
1628     }
1629   }
1630
1631   @Override
1632   public AlignmentAnnotation[] getAnnotation(String label)
1633   {
1634     if (annotation == null || annotation.size() == 0)
1635     {
1636       return null;
1637     }
1638
1639     Vector<AlignmentAnnotation> subset = new Vector<>();
1640     Enumeration<AlignmentAnnotation> e = annotation.elements();
1641     while (e.hasMoreElements())
1642     {
1643       AlignmentAnnotation ann = e.nextElement();
1644       if (ann.label != null && ann.label.equals(label))
1645       {
1646         subset.addElement(ann);
1647       }
1648     }
1649     if (subset.size() == 0)
1650     {
1651       return null;
1652     }
1653     AlignmentAnnotation[] anns = new AlignmentAnnotation[subset.size()];
1654     int i = 0;
1655     e = subset.elements();
1656     while (e.hasMoreElements())
1657     {
1658       anns[i++] = e.nextElement();
1659     }
1660     subset.removeAllElements();
1661     return anns;
1662   }
1663
1664   @Override
1665   public boolean updatePDBIds()
1666   {
1667     if (datasetSequence != null)
1668     {
1669       // TODO: could merge DBRefs
1670       return datasetSequence.updatePDBIds();
1671     }
1672     if (dbrefs == null || dbrefs.length == 0)
1673     {
1674       return false;
1675     }
1676     boolean added = false;
1677     for (DBRefEntry dbr : dbrefs)
1678     {
1679       if (DBRefSource.PDB.equals(dbr.getSource()))
1680       {
1681         /*
1682          * 'Add' any PDB dbrefs as a PDBEntry - add is only performed if the
1683          * PDB id is not already present in a 'matching' PDBEntry
1684          * Constructor parses out a chain code if appended to the accession id
1685          * (a fudge used to 'store' the chain code in the DBRef)
1686          */
1687         PDBEntry pdbe = new PDBEntry(dbr);
1688         added |= addPDBId(pdbe);
1689       }
1690     }
1691     return added;
1692   }
1693
1694   @Override
1695   public void transferAnnotation(SequenceI entry, Mapping mp)
1696   {
1697     if (datasetSequence != null)
1698     {
1699       datasetSequence.transferAnnotation(entry, mp);
1700       return;
1701     }
1702     if (entry.getDatasetSequence() != null)
1703     {
1704       transferAnnotation(entry.getDatasetSequence(), mp);
1705       return;
1706     }
1707     // transfer any new features from entry onto sequence
1708     if (entry.getSequenceFeatures() != null)
1709     {
1710
1711       List<SequenceFeature> sfs = entry.getSequenceFeatures();
1712       for (SequenceFeature feature : sfs)
1713       {
1714        SequenceFeature sf[] = (mp != null) ? mp.locateFeature(feature)
1715                 : new SequenceFeature[] { new SequenceFeature(feature) };
1716         if (sf != null)
1717         {
1718           for (int sfi = 0; sfi < sf.length; sfi++)
1719           {
1720             addSequenceFeature(sf[sfi]);
1721           }
1722         }
1723       }
1724     }
1725
1726     // transfer PDB entries
1727     if (entry.getAllPDBEntries() != null)
1728     {
1729       Enumeration<PDBEntry> e = entry.getAllPDBEntries().elements();
1730       while (e.hasMoreElements())
1731       {
1732         PDBEntry pdb = e.nextElement();
1733         addPDBId(pdb);
1734       }
1735     }
1736     // transfer database references
1737     DBRefEntry[] entryRefs = entry.getDBRefs();
1738     if (entryRefs != null)
1739     {
1740       for (int r = 0; r < entryRefs.length; r++)
1741       {
1742         DBRefEntry newref = new DBRefEntry(entryRefs[r]);
1743         if (newref.getMap() != null && mp != null)
1744         {
1745           // remap ref using our local mapping
1746         }
1747         // we also assume all version string setting is done by dbSourceProxy
1748         /*
1749          * if (!newref.getSource().equalsIgnoreCase(dbSource)) {
1750          * newref.setSource(dbSource); }
1751          */
1752         addDBRef(newref);
1753       }
1754     }
1755   }
1756
1757   @Override
1758   public void setRNA(RNA r)
1759   {
1760     rna = r;
1761   }
1762
1763   @Override
1764   public RNA getRNA()
1765   {
1766     return rna;
1767   }
1768
1769   @Override
1770   public List<AlignmentAnnotation> getAlignmentAnnotations(String calcId,
1771           String label)
1772   {
1773     List<AlignmentAnnotation> result = new ArrayList<>();
1774     if (this.annotation != null)
1775     {
1776       for (AlignmentAnnotation ann : annotation)
1777       {
1778         if (ann.calcId != null && ann.calcId.equals(calcId)
1779                 && ann.label != null && ann.label.equals(label))
1780         {
1781           result.add(ann);
1782         }
1783       }
1784     }
1785     return result;
1786   }
1787
1788   @Override
1789   public String toString()
1790   {
1791     return getDisplayId(false);
1792   }
1793
1794   @Override
1795   public PDBEntry getPDBEntry(String pdbIdStr)
1796   {
1797     if (getDatasetSequence() != null)
1798     {
1799       return getDatasetSequence().getPDBEntry(pdbIdStr);
1800     }
1801     if (pdbIds == null)
1802     {
1803       return null;
1804     }
1805     List<PDBEntry> entries = getAllPDBEntries();
1806     for (PDBEntry entry : entries)
1807     {
1808       if (entry.getId().equalsIgnoreCase(pdbIdStr))
1809       {
1810         return entry;
1811       }
1812     }
1813     return null;
1814   }
1815
1816   @Override
1817   public List<DBRefEntry> getPrimaryDBRefs()
1818   {
1819     if (datasetSequence != null)
1820     {
1821       return datasetSequence.getPrimaryDBRefs();
1822     }
1823     if (dbrefs == null || dbrefs.length == 0)
1824     {
1825       return Collections.emptyList();
1826     }
1827     synchronized (dbrefs)
1828     {
1829       List<DBRefEntry> primaries = new ArrayList<>();
1830       DBRefEntry[] tmp = new DBRefEntry[1];
1831       for (DBRefEntry ref : dbrefs)
1832       {
1833         if (!ref.isPrimaryCandidate())
1834         {
1835           continue;
1836         }
1837         if (ref.hasMap())
1838         {
1839           MapList mp = ref.getMap().getMap();
1840           if (mp.getFromLowest() > start || mp.getFromHighest() < end)
1841           {
1842             // map only involves a subsequence, so cannot be primary
1843             continue;
1844           }
1845         }
1846         // whilst it looks like it is a primary ref, we also sanity check type
1847         if (DBRefUtils.getCanonicalName(DBRefSource.PDB)
1848                 .equals(DBRefUtils.getCanonicalName(ref.getSource())))
1849         {
1850           // PDB dbrefs imply there should be a PDBEntry associated
1851           // TODO: tighten PDB dbrefs
1852           // formally imply Jalview has actually downloaded and
1853           // parsed the pdb file. That means there should be a cached file
1854           // handle on the PDBEntry, and a real mapping between sequence and
1855           // extracted sequence from PDB file
1856           PDBEntry pdbentry = getPDBEntry(ref.getAccessionId());
1857           if (pdbentry != null && pdbentry.getFile() != null)
1858           {
1859             primaries.add(ref);
1860           }
1861           continue;
1862         }
1863         // check standard protein or dna sources
1864         tmp[0] = ref;
1865         DBRefEntry[] res = DBRefUtils.selectDbRefs(!isProtein(), tmp);
1866         if (res != null && res[0] == tmp[0])
1867         {
1868           primaries.add(ref);
1869           continue;
1870         }
1871       }
1872       return primaries;
1873     }
1874   }
1875
1876   /**
1877    * {@inheritDoc}
1878    */
1879   @Override
1880   public List<SequenceFeature> findFeatures(int fromColumn, int toColumn,
1881           String... types)
1882   {
1883     int startPos = findPosition(fromColumn - 1); // convert base 1 to base 0
1884     int endPos = fromColumn == toColumn ? startPos
1885             : findPosition(toColumn - 1);
1886
1887     List<SequenceFeature> result = getFeatures().findFeatures(startPos,
1888             endPos, types);
1889
1890     /*
1891      * if end column is gapped, endPos may be to the right,
1892      * and we may have included adjacent or enclosing features;
1893      * remove any that are not enclosing, non-contact features
1894      */
1895     boolean endColumnIsGapped = toColumn > 0 && toColumn <= sequence.length
1896             && Comparison.isGap(sequence[toColumn - 1]);
1897     if (endPos > this.end || endColumnIsGapped)
1898     {
1899       ListIterator<SequenceFeature> it = result.listIterator();
1900       while (it.hasNext())
1901       {
1902         SequenceFeature sf = it.next();
1903         int sfBegin = sf.getBegin();
1904         int sfEnd = sf.getEnd();
1905         int featureStartColumn = findIndex(sfBegin);
1906         if (featureStartColumn > toColumn)
1907         {
1908           it.remove();
1909         }
1910         else if (featureStartColumn < fromColumn)
1911         {
1912           int featureEndColumn = sfEnd == sfBegin ? featureStartColumn
1913                   : findIndex(sfEnd);
1914           if (featureEndColumn < fromColumn)
1915           {
1916             it.remove();
1917           }
1918           else if (featureEndColumn > toColumn && sf.isContactFeature())
1919           {
1920             /*
1921              * remove an enclosing feature if it is a contact feature
1922              */
1923             it.remove();
1924           }
1925         }
1926       }
1927     }
1928
1929     return result;
1930   }
1931
1932   /**
1933    * Invalidates any stale cursors (forcing recalculation) by incrementing the
1934    * token that has to match the one presented by the cursor
1935    */
1936   @Override
1937   public void sequenceChanged()
1938   {
1939     changeCount++;
1940   }
1941
1942   /**
1943    * {@inheritDoc}
1944    */
1945   @Override
1946   public int replace(char c1, char c2)
1947   {
1948     if (c1 == c2)
1949     {
1950       return 0;
1951     }
1952     int count = 0;
1953     synchronized (sequence)
1954     {
1955       for (int c = 0; c < sequence.length; c++)
1956       {
1957         if (sequence[c] == c1)
1958         {
1959           sequence[c] = c2;
1960           count++;
1961         }
1962       }
1963     }
1964     if (count > 0)
1965     {
1966       sequenceChanged();
1967     }
1968
1969     return count;
1970   }
1971
1972   @Override
1973   public String getSequenceStringFromIterator(Iterator<int[]> it)
1974   {
1975     StringBuilder newSequence = new StringBuilder();
1976     while (it.hasNext())
1977     {
1978       int[] block = it.next();
1979       if (it.hasNext())
1980       {
1981         newSequence.append(getSequence(block[0], block[1] + 1));
1982       }
1983       else
1984       {
1985         newSequence.append(getSequence(block[0], block[1]));
1986       }
1987     }
1988
1989     return newSequence.toString();
1990   }
1991
1992   @Override
1993   public int firstResidueOutsideIterator(Iterator<int[]> regions)
1994   {
1995     int start = 0;
1996
1997     if (!regions.hasNext())
1998     {
1999       return findIndex(getStart()) - 1;
2000     }
2001
2002     // Simply walk along the sequence whilst watching for region
2003     // boundaries
2004     int hideStart = getLength();
2005     int hideEnd = -1;
2006     boolean foundStart = false;
2007
2008     // step through the non-gapped positions of the sequence
2009     for (int i = getStart(); i <= getEnd() && (!foundStart); i++)
2010     {
2011       // get alignment position of this residue in the sequence
2012       int p = findIndex(i) - 1;
2013
2014       // update region start/end
2015       while (hideEnd < p && regions.hasNext())
2016       {
2017         int[] region = regions.next();
2018         hideStart = region[0];
2019         hideEnd = region[1];
2020       }
2021       if (hideEnd < p)
2022       {
2023         hideStart = getLength();
2024       }
2025       // update boundary for sequence
2026       if (p < hideStart)
2027       {
2028         start = p;
2029         foundStart = true;
2030       }
2031     }
2032
2033     if (foundStart)
2034     {
2035       return start;
2036     }
2037     // otherwise, sequence was completely hidden
2038     return 0;
2039   }
2040 }