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   }
 501
 502   /**
 503    * DOCUMENT ME!
 504    *
 505    * @return DOCUMENT ME!
 506    */
 507   @Override
 508   public int getStart()
 509   {
 510     return this.start;
 511   }
 512
 513   /**
 514    * DOCUMENT ME!
 515    *
 516    * @param end
 517    *          DOCUMENT ME!
 518    */
 519   @Override
 520   public void setEnd(int end)
 521   {
 522     this.end = end;
 523   }
 524
 525   /**
 526    * DOCUMENT ME!
 527    *
 528    * @return DOCUMENT ME!
 529    */
 530   @Override
 531   public int getEnd()
 532   {
 533     return this.end;
 534   }
 535
 536   /**
 537    * DOCUMENT ME!
 538    *
 539    * @return DOCUMENT ME!
 540    */
 541   @Override
 542   public int getLength()
 543   {
 544     return this.sequence.length;
 545   }
 546
 547   /**
 548    * DOCUMENT ME!
 549    *
 550    * @param seq
 551    *          DOCUMENT ME!
 552    */
 553   @Override
 554   public void setSequence(String seq)
 555   {
 556     this.sequence = seq.toCharArray();
 557     checkValidRange();
 558     sequenceChanged();
 559   }
 560
 561   @Override
 562   public String getSequenceAsString()
 563   {
 564     return new String(sequence);
 565   }
 566
 567   @Override
 568   public String getSequenceAsString(int start, int end)
 569   {
 570     return new String(getSequence(start, end));
 571   }
 572
 573   @Override
 574   public char[] getSequence()
 575   {
 576     // return sequence;
 577     return sequence == null ? null : Arrays.copyOf(sequence,
 578             sequence.length);
 579   }
 580
 581   /*
 582    * (non-Javadoc)
 583    *
 584    * @see jalview.datamodel.SequenceI#getSequence(int, int)
 585    */
 586   @Override
 587   public char[] getSequence(int start, int end)
 588   {
 589     if (start < 0)
 590     {
 591       start = 0;
 592     }
 593     // JBPNote - left to user to pad the result here (TODO:Decide on this
 594     // policy)
 595     if (start >= sequence.length)
 596     {
 597       return new char[0];
 598     }
 599
 600     if (end >= sequence.length)
 601     {
 602       end = sequence.length;
 603     }
 604
 605     char[] reply = new char[end - start];
 606     System.arraycopy(sequence, start, reply, 0, end - start);
 607
 608     return reply;
 609   }
 610
 611   @Override
 612   public SequenceI getSubSequence(int start, int end)
 613   {
 614     if (start < 0)
 615     {
 616       start = 0;
 617     }
 618     char[] seq = getSequence(start, end);
 619     if (seq.length == 0)
 620     {
 621       return null;
 622     }
 623     int nstart = findPosition(start);
 624     int nend = findPosition(end) - 1;
 625     // JBPNote - this is an incomplete copy.
 626     SequenceI nseq = new Sequence(this.getName(), seq, nstart, nend);
 627     nseq.setDescription(description);
 628     if (datasetSequence != null)
 629     {
 630       nseq.setDatasetSequence(datasetSequence);
 631     }
 632     else
 633     {
 634       nseq.setDatasetSequence(this);
 635     }
 636     return nseq;
 637   }
 638
 639   /**
 640    * Returns the character of the aligned sequence at the given position (base
 641    * zero), or space if the position is not within the sequence's bounds
 642    *
 643    * @return
 644    */
 645   @Override
 646   public char getCharAt(int i)
 647   {
 648     if (i >= 0 && i < sequence.length)
 649     {
 650       return sequence[i];
 651     }
 652     else
 653     {
 654       return ' ';
 655     }
 656   }
 657
 658   /**
 659    * Sets the sequence description, and also parses out any special formats of
 660    * interest
 661    *
 662    * @param desc
 663    */
 664   @Override
 665   public void setDescription(String desc)
 666   {
 667     this.description = desc;
 668   }
 669
 670   @Override
 671   public void setGeneLoci(String speciesId, String assemblyId,
 672           String chromosomeId, MapList map)
 673   {
 674     addDBRef(new GeneLocus(speciesId, assemblyId, chromosomeId,
 675             new Mapping(map)));
 676   }
 677
 678   /**
 679    * Returns the gene loci mapping for the sequence (may be null)
 680    *
 681    * @return
 682    */
 683   @Override
 684   public GeneLociI getGeneLoci()
 685   {
 686     DBRefEntry[] refs = getDBRefs();
 687     if (refs != null)
 688     {
 689       for (final DBRefEntry ref : refs)
 690       {
 691         if (ref instanceof GeneLociI)
 692         {
 693           return (GeneLociI) ref;
 694         }
 695       }
 696     }
 697     return null;
 698   }
 699
 700   /**
 701    * Answers the description
 702    *
 703    * @return
 704    */
 705   @Override
 706   public String getDescription()
 707   {
 708     return this.description;
 709   }
 710
 711   /**
 712    * {@inheritDoc}
 713    */
 714   @Override
 715   public int findIndex(int pos)
 716   {
 717     /*
 718      * use a valid, hopefully nearby, cursor if available
 719      */
 720     if (isValidCursor(cursor))
 721     {
 722       return findIndex(pos, cursor);
 723     }
 724
 725     int j = start;
 726     int i = 0;
 727     int startColumn = 0;
 728
 729     /*
 730      * traverse sequence from the start counting gaps; make a note of
 731      * the column of the first residue to save in the cursor
 732      */
 733     while ((i < sequence.length) && (j <= end) && (j <= pos))
 734     {
 735       if (!Comparison.isGap(sequence[i]))
 736       {
 737         if (j == start)
 738         {
 739           startColumn = i;
 740         }
 741         j++;
 742       }
 743       i++;
 744     }
 745
 746     if (j == end && j < pos)
 747     {
 748       return end + 1;
 749     }
 750
 751     updateCursor(pos, i, startColumn);
 752     return i;
 753   }
 754
 755   /**
 756    * Updates the cursor to the latest found residue and column position
 757    *
 758    * @param residuePos
 759    *          (start..)
 760    * @param column
 761    *          (1..)
 762    * @param startColumn
 763    *          column position of the first sequence residue
 764    */
 765   protected void updateCursor(int residuePos, int column, int startColumn)
 766   {
 767     /*
 768      * preserve end residue column provided cursor was valid
 769      */
 770     int endColumn = isValidCursor(cursor) ? cursor.lastColumnPosition : 0;
 771
 772     if (residuePos == this.end)
 773     {
 774       endColumn = column;
 775     }
 776
 777     cursor = new SequenceCursor(this, residuePos, column, startColumn,
 778             endColumn, this.changeCount);
 779   }
 780
 781   /**
 782    * Answers the aligned column position (1..) for the given residue position
 783    * (start..) given a 'hint' of a residue/column location in the neighbourhood.
 784    * The hint may be left of, at, or to the right of the required position.
 785    *
 786    * @param pos
 787    * @param curs
 788    * @return
 789    */
 790   protected int findIndex(final int pos, SequenceCursor curs)
 791   {
 792     if (!isValidCursor(curs))
 793     {
 794       /*
 795        * wrong or invalidated cursor, compute de novo
 796        */
 797       return findIndex(pos);
 798     }
 799
 800     if (curs.residuePosition == pos)
 801     {
 802       return curs.columnPosition;
 803     }
 804
 805     /*
 806      * move left or right to find pos from hint.position
 807      */
 808     int col = curs.columnPosition - 1; // convert from base 1 to base 0
 809     int newPos = curs.residuePosition;
 810     int delta = newPos > pos ? -1 : 1;
 811
 812     while (newPos != pos)
 813     {
 814       col += delta; // shift one column left or right
 815       if (col < 0)
 816       {
 817         break;
 818       }
 819       if (col == sequence.length)
 820       {
 821         col--; // return last column if we failed to reach pos
 822         break;
 823       }
 824       if (!Comparison.isGap(sequence[col]))
 825       {
 826         newPos += delta;
 827       }
 828     }
 829
 830     col++; // convert back to base 1
 831
 832     /*
 833      * only update cursor if we found the target position
 834      */
 835     if (newPos == pos)
 836     {
 837       updateCursor(pos, col, curs.firstColumnPosition);
 838     }
 839
 840     return col;
 841   }
 842
 843   /**
 844    * {@inheritDoc}
 845    */
 846   @Override
 847   public int findPosition(final int column)
 848   {
 849     /*
 850      * use a valid, hopefully nearby, cursor if available
 851      */
 852     if (isValidCursor(cursor))
 853     {
 854       return findPosition(column + 1, cursor);
 855     }
 856
 857     // TODO recode this more naturally i.e. count residues only
 858     // as they are found, not 'in anticipation'
 859
 860     /*
 861      * traverse the sequence counting gaps; note the column position
 862      * of the first residue, to save in the cursor
 863      */
 864     int firstResidueColumn = 0;
 865     int lastPosFound = 0;
 866     int lastPosFoundColumn = 0;
 867     int seqlen = sequence.length;
 868
 869     if (seqlen > 0 && !Comparison.isGap(sequence[0]))
 870     {
 871       lastPosFound = start;
 872       lastPosFoundColumn = 0;
 873     }
 874
 875     int j = 0;
 876     int pos = start;
 877
 878     while (j < column && j < seqlen)
 879     {
 880       if (!Comparison.isGap(sequence[j]))
 881       {
 882         lastPosFound = pos;
 883         lastPosFoundColumn = j;
 884         if (pos == this.start)
 885         {
 886           firstResidueColumn = j;
 887         }
 888         pos++;
 889       }
 890       j++;
 891     }
 892     if (j < seqlen && !Comparison.isGap(sequence[j]))
 893     {
 894       lastPosFound = pos;
 895       lastPosFoundColumn = j;
 896       if (pos == this.start)
 897       {
 898         firstResidueColumn = j;
 899       }
 900     }
 901
 902     /*
 903      * update the cursor to the last residue position found (if any)
 904      * (converting column position to base 1)
 905      */
 906     if (lastPosFound != 0)
 907     {
 908       updateCursor(lastPosFound, lastPosFoundColumn + 1,
 909               firstResidueColumn + 1);
 910     }
 911
 912     return pos;
 913   }
 914
 915   /**
 916    * Answers true if the given cursor is not null, is for this sequence object,
 917    * and has a token value that matches this object's changeCount, else false.
 918    * This allows us to ignore a cursor as 'stale' if the sequence has been
 919    * modified since the cursor was created.
 920    *
 921    * @param curs
 922    * @return
 923    */
 924   protected boolean isValidCursor(SequenceCursor curs)
 925   {
 926     if (curs == null || curs.sequence != this || curs.token != changeCount)
 927     {
 928       return false;
 929     }
 930     /*
 931      * sanity check against range
 932      */
 933     if (curs.columnPosition < 0 || curs.columnPosition > sequence.length)
 934     {
 935       return false;
 936     }
 937     if (curs.residuePosition < start || curs.residuePosition > end)
 938     {
 939       return false;
 940     }
 941     return true;
 942   }
 943
 944   /**
 945    * Answers the sequence position (start..) for the given aligned column
 946    * position (1..), given a hint of a cursor in the neighbourhood. The cursor
 947    * may lie left of, at, or to the right of the column position.
 948    *
 949    * @param col
 950    * @param curs
 951    * @return
 952    */
 953   protected int findPosition(final int col, SequenceCursor curs)
 954   {
 955     if (!isValidCursor(curs))
 956     {
 957       /*
 958        * wrong or invalidated cursor, compute de novo
 959        */
 960       return findPosition(col - 1);// ugh back to base 0
 961     }
 962
 963     if (curs.columnPosition == col)
 964     {
 965       cursor = curs; // in case this method becomes public
 966       return curs.residuePosition; // easy case :-)
 967     }
 968
 969     if (curs.lastColumnPosition > 0 && curs.lastColumnPosition < col)
 970     {
 971       /*
 972        * sequence lies entirely to the left of col
 973        * - return last residue + 1
 974        */
 975       return end + 1;
 976     }
 977
 978     if (curs.firstColumnPosition > 0 && curs.firstColumnPosition > col)
 979     {
 980       /*
 981        * sequence lies entirely to the right of col
 982        * - return first residue
 983        */
 984       return start;
 985     }
 986
 987     // todo could choose closest to col out of column,
 988     // firstColumnPosition, lastColumnPosition as a start point
 989
 990     /*
 991      * move left or right to find pos from cursor position
 992      */
 993     int firstResidueColumn = curs.firstColumnPosition;
 994     int column = curs.columnPosition - 1; // to base 0
 995     int newPos = curs.residuePosition;
 996     int delta = curs.columnPosition > col ? -1 : 1;
 997     boolean gapped = false;
 998     int lastFoundPosition = curs.residuePosition;
 999     int lastFoundPositionColumn = curs.columnPosition;
1000
1001     while (column != col - 1)
1002     {
1003       column += delta; // shift one column left or right
1004       if (column < 0 || column == sequence.length)
1005       {
1006         break;
1007       }
1008       gapped = Comparison.isGap(sequence[column]);
1009       if (!gapped)
1010       {
1011         newPos += delta;
1012         lastFoundPosition = newPos;
1013         lastFoundPositionColumn = column + 1;
1014         if (lastFoundPosition == this.start)
1015         {
1016           firstResidueColumn = column + 1;
1017         }
1018       }
1019     }
1020
1021     if (cursor == null || lastFoundPosition != cursor.residuePosition)
1022     {
1023       updateCursor(lastFoundPosition, lastFoundPositionColumn,
1024               firstResidueColumn);
1025     }
1026
1027     /*
1028      * hack to give position to the right if on a gap
1029      * or beyond the length of the sequence (see JAL-2562)
1030      */
1031     if (delta > 0 && (gapped || column >= sequence.length))
1032     {
1033       newPos++;
1034     }
1035
1036     return newPos;
1037   }
1038
1039   /**
1040    * {@inheritDoc}
1041    */
1042   @Override
1043   public ContiguousI findPositions(int fromColumn, int toColumn)
1044   {
1045     if (toColumn < fromColumn || fromColumn < 1)
1046     {
1047       return null;
1048     }
1049
1050     /*
1051      * find the first non-gapped position, if any
1052      */
1053     int firstPosition = 0;
1054     int col = fromColumn - 1;
1055     int length = sequence.length;
1056     while (col < length && col < toColumn)
1057     {
1058       if (!Comparison.isGap(sequence[col]))
1059       {
1060         firstPosition = findPosition(col++);
1061         break;
1062       }
1063       col++;
1064     }
1065
1066     if (firstPosition == 0)
1067     {
1068       return null;
1069     }
1070
1071     /*
1072      * find the last non-gapped position
1073      */
1074     int lastPosition = firstPosition;
1075     while (col < length && col < toColumn)
1076     {
1077       if (!Comparison.isGap(sequence[col++]))
1078       {
1079         lastPosition++;
1080       }
1081     }
1082
1083     return new Range(firstPosition, lastPosition);
1084   }
1085
1086   /**
1087    * Returns an int array where indices correspond to each residue in the
1088    * sequence and the element value gives its position in the alignment
1089    *
1090    * @return int[SequenceI.getEnd()-SequenceI.getStart()+1] or null if no
1091    *         residues in SequenceI object
1092    */
1093   @Override
1094   public int[] gapMap()
1095   {
1096     String seq = jalview.analysis.AlignSeq.extractGaps(
1097             jalview.util.Comparison.GapChars, new String(sequence));
1098     int[] map = new int[seq.length()];
1099     int j = 0;
1100     int p = 0;
1101
1102     while (j < sequence.length)
1103     {
1104       if (!jalview.util.Comparison.isGap(sequence[j]))
1105       {
1106         map[p++] = j;
1107       }
1108
1109       j++;
1110     }
1111
1112     return map;
1113   }
1114
1115   /**
1116    * Build a bitset corresponding to sequence gaps
1117    *
1118    * @return a BitSet where set values correspond to gaps in the sequence
1119    */
1120   @Override
1121   public BitSet gapBitset()
1122   {
1123     BitSet gaps = new BitSet(sequence.length);
1124     int j = 0;
1125     while (j < sequence.length)
1126     {
1127       if (jalview.util.Comparison.isGap(sequence[j]))
1128       {
1129         gaps.set(j);
1130       }
1131       j++;
1132     }
1133     return gaps;
1134   }
1135
1136   @Override
1137   public int[] findPositionMap()
1138   {
1139     int map[] = new int[sequence.length];
1140     int j = 0;
1141     int pos = start;
1142     int seqlen = sequence.length;
1143     while ((j < seqlen))
1144     {
1145       map[j] = pos;
1146       if (!jalview.util.Comparison.isGap(sequence[j]))
1147       {
1148         pos++;
1149       }
1150
1151       j++;
1152     }
1153     return map;
1154   }
1155
1156   @Override
1157   public List<int[]> getInsertions()
1158   {
1159     ArrayList<int[]> map = new ArrayList<>();
1160     int lastj = -1, j = 0;
1161     int pos = start;
1162     int seqlen = sequence.length;
1163     while ((j < seqlen))
1164     {
1165       if (jalview.util.Comparison.isGap(sequence[j]))
1166       {
1167         if (lastj == -1)
1168         {
1169           lastj = j;
1170         }
1171       }
1172       else
1173       {
1174         if (lastj != -1)
1175         {
1176           map.add(new int[] { lastj, j - 1 });
1177           lastj = -1;
1178         }
1179       }
1180       j++;
1181     }
1182     if (lastj != -1)
1183     {
1184       map.add(new int[] { lastj, j - 1 });
1185       lastj = -1;
1186     }
1187     return map;
1188   }
1189
1190   @Override
1191   public BitSet getInsertionsAsBits()
1192   {
1193     BitSet map = new BitSet();
1194     int lastj = -1, j = 0;
1195     int pos = start;
1196     int seqlen = sequence.length;
1197     while ((j < seqlen))
1198     {
1199       if (jalview.util.Comparison.isGap(sequence[j]))
1200       {
1201         if (lastj == -1)
1202         {
1203           lastj = j;
1204         }
1205       }
1206       else
1207       {
1208         if (lastj != -1)
1209         {
1210           map.set(lastj, j);
1211           lastj = -1;
1212         }
1213       }
1214       j++;
1215     }
1216     if (lastj != -1)
1217     {
1218       map.set(lastj, j);
1219       lastj = -1;
1220     }
1221     return map;
1222   }
1223
1224   @Override
1225   public void deleteChars(final int i, final int j)
1226   {
1227     int newstart = start, newend = end;
1228     if (i >= sequence.length || i < 0)
1229     {
1230       return;
1231     }
1232
1233     char[] tmp = StringUtils.deleteChars(sequence, i, j);
1234     boolean createNewDs = false;
1235     // TODO: take a (second look) at the dataset creation validation method for
1236     // the very large sequence case
1237
1238     int startIndex = findIndex(start) - 1;
1239     int endIndex = findIndex(end) - 1;
1240     int startDeleteColumn = -1; // for dataset sequence deletions
1241     int deleteCount = 0;
1242
1243     for (int s = i; s < j && s < sequence.length; s++)
1244     {
1245       if (Comparison.isGap(sequence[s]))
1246       {
1247         continue;
1248       }
1249       deleteCount++;
1250       if (startDeleteColumn == -1)
1251       {
1252         startDeleteColumn = findPosition(s) - start;
1253       }
1254       if (createNewDs)
1255       {
1256         newend--;
1257       }
1258       else
1259       {
1260         if (startIndex == s)
1261         {
1262           /*
1263            * deleting characters from start of sequence; new start is the
1264            * sequence position of the next column (position to the right
1265            * if the column position is gapped)
1266            */
1267           newstart = findPosition(j);
1268           break;
1269         }
1270         else
1271         {
1272           if (endIndex < j)
1273           {
1274             /*
1275              * deleting characters at end of sequence; new end is the sequence
1276              * position of the column before the deletion; subtract 1 if this is
1277              * gapped since findPosition returns the next sequence position
1278              */
1279             newend = findPosition(i - 1);
1280             if (Comparison.isGap(sequence[i - 1]))
1281             {
1282               newend--;
1283             }
1284             break;
1285           }
1286           else
1287           {
1288             createNewDs = true;
1289             newend--;
1290           }
1291         }
1292       }
1293     }
1294
1295     if (createNewDs && this.datasetSequence != null)
1296     {
1297       /*
1298        * if deletion occured in the middle of the sequence,
1299        * construct a new dataset sequence and delete the residues
1300        * that were deleted from the aligned sequence
1301        */
1302       Sequence ds = new Sequence(datasetSequence);
1303       ds.deleteChars(startDeleteColumn, startDeleteColumn + deleteCount);
1304       datasetSequence = ds;
1305       // TODO: remove any non-inheritable properties ?
1306       // TODO: create a sequence mapping (since there is a relation here ?)
1307     }
1308     start = newstart;
1309     end = newend;
1310     sequence = tmp;
1311     sequenceChanged();
1312   }
1313
1314   @Override
1315   public void insertCharAt(int i, int length, char c)
1316   {
1317     char[] tmp = new char[sequence.length + length];
1318
1319     if (i >= sequence.length)
1320     {
1321       System.arraycopy(sequence, 0, tmp, 0, sequence.length);
1322       i = sequence.length;
1323     }
1324     else
1325     {
1326       System.arraycopy(sequence, 0, tmp, 0, i);
1327     }
1328
1329     int index = i;
1330     while (length > 0)
1331     {
1332       tmp[index++] = c;
1333       length--;
1334     }
1335
1336     if (i < sequence.length)
1337     {
1338       System.arraycopy(sequence, i, tmp, index, sequence.length - i);
1339     }
1340
1341     sequence = tmp;
1342     sequenceChanged();
1343   }
1344
1345   @Override
1346   public void insertCharAt(int i, char c)
1347   {
1348     insertCharAt(i, 1, c);
1349   }
1350
1351   @Override
1352   public String getVamsasId()
1353   {
1354     return vamsasId;
1355   }
1356
1357   @Override
1358   public void setVamsasId(String id)
1359   {
1360     vamsasId = id;
1361   }
1362
1363   @Override
1364   public void setDBRefs(DBRefEntry[] dbref)
1365   {
1366     if (dbrefs == null && datasetSequence != null
1367             && this != datasetSequence)
1368     {
1369       datasetSequence.setDBRefs(dbref);
1370       return;
1371     }
1372     dbrefs = dbref;
1373     if (dbrefs != null)
1374     {
1375       DBRefUtils.ensurePrimaries(this);
1376     }
1377   }
1378
1379   @Override
1380   public DBRefEntry[] getDBRefs()
1381   {
1382     if (dbrefs == null && datasetSequence != null
1383             && this != datasetSequence)
1384     {
1385       return datasetSequence.getDBRefs();
1386     }
1387     return dbrefs;
1388   }
1389
1390   @Override
1391   public void addDBRef(DBRefEntry entry)
1392   {
1393     if (datasetSequence != null)
1394     {
1395       datasetSequence.addDBRef(entry);
1396       return;
1397     }
1398
1399     if (dbrefs == null)
1400     {
1401       dbrefs = new DBRefEntry[0];
1402     }
1403
1404     for (DBRefEntryI dbr : dbrefs)
1405     {
1406       if (dbr.updateFrom(entry))
1407       {
1408         /*
1409          * found a dbref that either matched, or could be
1410          * updated from, the new entry - no need to add it
1411          */
1412         return;
1413       }
1414     }
1415
1416     /*
1417      * extend the array to make room for one more
1418      */
1419     // TODO use an ArrayList instead
1420     int j = dbrefs.length;
1421     DBRefEntry[] temp = new DBRefEntry[j + 1];
1422     System.arraycopy(dbrefs, 0, temp, 0, j);
1423     temp[temp.length - 1] = entry;
1424
1425     dbrefs = temp;
1426
1427     DBRefUtils.ensurePrimaries(this);
1428   }
1429
1430   @Override
1431   public void setDatasetSequence(SequenceI seq)
1432   {
1433     if (seq == this)
1434     {
1435       throw new IllegalArgumentException(
1436               "Implementation Error: self reference passed to SequenceI.setDatasetSequence");
1437     }
1438     if (seq != null && seq.getDatasetSequence() != null)
1439     {
1440       throw new IllegalArgumentException(
1441               "Implementation error: cascading dataset sequences are not allowed.");
1442     }
1443     datasetSequence = seq;
1444   }
1445
1446   @Override
1447   public SequenceI getDatasetSequence()
1448   {
1449     return datasetSequence;
1450   }
1451
1452   @Override
1453   public AlignmentAnnotation[] getAnnotation()
1454   {
1455     return annotation == null ? null
1456             : annotation
1457                     .toArray(new AlignmentAnnotation[annotation.size()]);
1458   }
1459
1460   @Override
1461   public boolean hasAnnotation(AlignmentAnnotation ann)
1462   {
1463     return annotation == null ? false : annotation.contains(ann);
1464   }
1465
1466   @Override
1467   public void addAlignmentAnnotation(AlignmentAnnotation annotation)
1468   {
1469     if (this.annotation == null)
1470     {
1471       this.annotation = new Vector<>();
1472     }
1473     if (!this.annotation.contains(annotation))
1474     {
1475       this.annotation.addElement(annotation);
1476     }
1477     annotation.setSequenceRef(this);
1478   }
1479
1480   @Override
1481   public void removeAlignmentAnnotation(AlignmentAnnotation annotation)
1482   {
1483     if (this.annotation != null)
1484     {
1485       this.annotation.removeElement(annotation);
1486       if (this.annotation.size() == 0)
1487       {
1488         this.annotation = null;
1489       }
1490     }
1491   }
1492
1493   /**
1494    * test if this is a valid candidate for another sequence's dataset sequence.
1495    *
1496    */
1497   private boolean isValidDatasetSequence()
1498   {
1499     if (datasetSequence != null)
1500     {
1501       return false;
1502     }
1503     for (int i = 0; i < sequence.length; i++)
1504     {
1505       if (jalview.util.Comparison.isGap(sequence[i]))
1506       {
1507         return false;
1508       }
1509     }
1510     return true;
1511   }
1512
1513   @Override
1514   public SequenceI deriveSequence()
1515   {
1516     Sequence seq = null;
1517     if (datasetSequence == null)
1518     {
1519       if (isValidDatasetSequence())
1520       {
1521         // Use this as dataset sequence
1522         seq = new Sequence(getName(), "", 1, -1);
1523         seq.setDatasetSequence(this);
1524         seq.initSeqFrom(this, getAnnotation());
1525         return seq;
1526       }
1527       else
1528       {
1529         // Create a new, valid dataset sequence
1530         createDatasetSequence();
1531       }
1532     }
1533     return new Sequence(this);
1534   }
1535
1536   private boolean _isNa;
1537
1538   private int _seqhash = 0;
1539
1540   /**
1541    * Answers false if the sequence is more than 85% nucleotide (ACGTU), else
1542    * true
1543    */
1544   @Override
1545   public boolean isProtein()
1546   {
1547     if (datasetSequence != null)
1548     {
1549       return datasetSequence.isProtein();
1550     }
1551     if (_seqhash != sequence.hashCode())
1552     {
1553       _seqhash = sequence.hashCode();
1554       _isNa = Comparison.isNucleotide(this);
1555     }
1556     return !_isNa;
1557   };
1558
1559   /*
1560    * (non-Javadoc)
1561    *
1562    * @see jalview.datamodel.SequenceI#createDatasetSequence()
1563    */
1564   @Override
1565   public SequenceI createDatasetSequence()
1566   {
1567     if (datasetSequence == null)
1568     {
1569       Sequence dsseq = new Sequence(getName(),
1570               AlignSeq.extractGaps(jalview.util.Comparison.GapChars,
1571                       getSequenceAsString()),
1572               getStart(), getEnd());
1573
1574       datasetSequence = dsseq;
1575
1576       dsseq.setDescription(description);
1577       // move features and database references onto dataset sequence
1578       dsseq.sequenceFeatureStore = sequenceFeatureStore;
1579       sequenceFeatureStore = null;
1580       dsseq.dbrefs = dbrefs;
1581       dbrefs = null;
1582       // TODO: search and replace any references to this sequence with
1583       // references to the dataset sequence in Mappings on dbref
1584       dsseq.pdbIds = pdbIds;
1585       pdbIds = null;
1586       datasetSequence.updatePDBIds();
1587       if (annotation != null)
1588       {
1589         // annotation is cloned rather than moved, to preserve what's currently
1590         // on the alignment
1591         for (AlignmentAnnotation aa : annotation)
1592         {
1593           AlignmentAnnotation _aa = new AlignmentAnnotation(aa);
1594           _aa.sequenceRef = datasetSequence;
1595           _aa.adjustForAlignment(); // uses annotation's own record of
1596                                     // sequence-column mapping
1597           datasetSequence.addAlignmentAnnotation(_aa);
1598         }
1599       }
1600     }
1601     return datasetSequence;
1602   }
1603
1604   /*
1605    * (non-Javadoc)
1606    *
1607    * @see
1608    * jalview.datamodel.SequenceI#setAlignmentAnnotation(AlignmmentAnnotation[]
1609    * annotations)
1610    */
1611   @Override
1612   public void setAlignmentAnnotation(AlignmentAnnotation[] annotations)
1613   {
1614     if (annotation != null)
1615     {
1616       annotation.removeAllElements();
1617     }
1618     if (annotations != null)
1619     {
1620       for (int i = 0; i < annotations.length; i++)
1621       {
1622         if (annotations[i] != null)
1623         {
1624           addAlignmentAnnotation(annotations[i]);
1625         }
1626       }
1627     }
1628   }
1629
1630   @Override
1631   public AlignmentAnnotation[] getAnnotation(String label)
1632   {
1633     if (annotation == null || annotation.size() == 0)
1634     {
1635       return null;
1636     }
1637
1638     Vector<AlignmentAnnotation> subset = new Vector<>();
1639     Enumeration<AlignmentAnnotation> e = annotation.elements();
1640     while (e.hasMoreElements())
1641     {
1642       AlignmentAnnotation ann = e.nextElement();
1643       if (ann.label != null && ann.label.equals(label))
1644       {
1645         subset.addElement(ann);
1646       }
1647     }
1648     if (subset.size() == 0)
1649     {
1650       return null;
1651     }
1652     AlignmentAnnotation[] anns = new AlignmentAnnotation[subset.size()];
1653     int i = 0;
1654     e = subset.elements();
1655     while (e.hasMoreElements())
1656     {
1657       anns[i++] = e.nextElement();
1658     }
1659     subset.removeAllElements();
1660     return anns;
1661   }
1662
1663   @Override
1664   public boolean updatePDBIds()
1665   {
1666     if (datasetSequence != null)
1667     {
1668       // TODO: could merge DBRefs
1669       return datasetSequence.updatePDBIds();
1670     }
1671     if (dbrefs == null || dbrefs.length == 0)
1672     {
1673       return false;
1674     }
1675     boolean added = false;
1676     for (DBRefEntry dbr : dbrefs)
1677     {
1678       if (DBRefSource.PDB.equals(dbr.getSource()))
1679       {
1680         /*
1681          * 'Add' any PDB dbrefs as a PDBEntry - add is only performed if the
1682          * PDB id is not already present in a 'matching' PDBEntry
1683          * Constructor parses out a chain code if appended to the accession id
1684          * (a fudge used to 'store' the chain code in the DBRef)
1685          */
1686         PDBEntry pdbe = new PDBEntry(dbr);
1687         added |= addPDBId(pdbe);
1688       }
1689     }
1690     return added;
1691   }
1692
1693   @Override
1694   public void transferAnnotation(SequenceI entry, Mapping mp)
1695   {
1696     if (datasetSequence != null)
1697     {
1698       datasetSequence.transferAnnotation(entry, mp);
1699       return;
1700     }
1701     if (entry.getDatasetSequence() != null)
1702     {
1703       transferAnnotation(entry.getDatasetSequence(), mp);
1704       return;
1705     }
1706     // transfer any new features from entry onto sequence
1707     if (entry.getSequenceFeatures() != null)
1708     {
1709
1710       List<SequenceFeature> sfs = entry.getSequenceFeatures();
1711       for (SequenceFeature feature : sfs)
1712       {
1713        SequenceFeature sf[] = (mp != null) ? mp.locateFeature(feature)
1714                 : new SequenceFeature[] { new SequenceFeature(feature) };
1715         if (sf != null)
1716         {
1717           for (int sfi = 0; sfi < sf.length; sfi++)
1718           {
1719             addSequenceFeature(sf[sfi]);
1720           }
1721         }
1722       }
1723     }
1724
1725     // transfer PDB entries
1726     if (entry.getAllPDBEntries() != null)
1727     {
1728       Enumeration<PDBEntry> e = entry.getAllPDBEntries().elements();
1729       while (e.hasMoreElements())
1730       {
1731         PDBEntry pdb = e.nextElement();
1732         addPDBId(pdb);
1733       }
1734     }
1735     // transfer database references
1736     DBRefEntry[] entryRefs = entry.getDBRefs();
1737     if (entryRefs != null)
1738     {
1739       for (int r = 0; r < entryRefs.length; r++)
1740       {
1741         DBRefEntry newref = new DBRefEntry(entryRefs[r]);
1742         if (newref.getMap() != null && mp != null)
1743         {
1744           // remap ref using our local mapping
1745         }
1746         // we also assume all version string setting is done by dbSourceProxy
1747         /*
1748          * if (!newref.getSource().equalsIgnoreCase(dbSource)) {
1749          * newref.setSource(dbSource); }
1750          */
1751         addDBRef(newref);
1752       }
1753     }
1754   }
1755
1756   @Override
1757   public void setRNA(RNA r)
1758   {
1759     rna = r;
1760   }
1761
1762   @Override
1763   public RNA getRNA()
1764   {
1765     return rna;
1766   }
1767
1768   @Override
1769   public List<AlignmentAnnotation> getAlignmentAnnotations(String calcId,
1770           String label)
1771   {
1772     List<AlignmentAnnotation> result = new ArrayList<>();
1773     if (this.annotation != null)
1774     {
1775       for (AlignmentAnnotation ann : annotation)
1776       {
1777         if (ann.calcId != null && ann.calcId.equals(calcId)
1778                 && ann.label != null && ann.label.equals(label))
1779         {
1780           result.add(ann);
1781         }
1782       }
1783     }
1784     return result;
1785   }
1786
1787   @Override
1788   public String toString()
1789   {
1790     return getDisplayId(false);
1791   }
1792
1793   @Override
1794   public PDBEntry getPDBEntry(String pdbIdStr)
1795   {
1796     if (getDatasetSequence() != null)
1797     {
1798       return getDatasetSequence().getPDBEntry(pdbIdStr);
1799     }
1800     if (pdbIds == null)
1801     {
1802       return null;
1803     }
1804     List<PDBEntry> entries = getAllPDBEntries();
1805     for (PDBEntry entry : entries)
1806     {
1807       if (entry.getId().equalsIgnoreCase(pdbIdStr))
1808       {
1809         return entry;
1810       }
1811     }
1812     return null;
1813   }
1814
1815   @Override
1816   public List<DBRefEntry> getPrimaryDBRefs()
1817   {
1818     if (datasetSequence != null)
1819     {
1820       return datasetSequence.getPrimaryDBRefs();
1821     }
1822     if (dbrefs == null || dbrefs.length == 0)
1823     {
1824       return Collections.emptyList();
1825     }
1826     synchronized (dbrefs)
1827     {
1828       List<DBRefEntry> primaries = new ArrayList<>();
1829       DBRefEntry[] tmp = new DBRefEntry[1];
1830       for (DBRefEntry ref : dbrefs)
1831       {
1832         if (!ref.isPrimaryCandidate())
1833         {
1834           continue;
1835         }
1836         if (ref.hasMap())
1837         {
1838           MapList mp = ref.getMap().getMap();
1839           if (mp.getFromLowest() > start || mp.getFromHighest() < end)
1840           {
1841             // map only involves a subsequence, so cannot be primary
1842             continue;
1843           }
1844         }
1845         // whilst it looks like it is a primary ref, we also sanity check type
1846         if (DBRefUtils.getCanonicalName(DBRefSource.PDB)
1847                 .equals(DBRefUtils.getCanonicalName(ref.getSource())))
1848         {
1849           // PDB dbrefs imply there should be a PDBEntry associated
1850           // TODO: tighten PDB dbrefs
1851           // formally imply Jalview has actually downloaded and
1852           // parsed the pdb file. That means there should be a cached file
1853           // handle on the PDBEntry, and a real mapping between sequence and
1854           // extracted sequence from PDB file
1855           PDBEntry pdbentry = getPDBEntry(ref.getAccessionId());
1856           if (pdbentry != null && pdbentry.getFile() != null)
1857           {
1858             primaries.add(ref);
1859           }
1860           continue;
1861         }
1862         // check standard protein or dna sources
1863         tmp[0] = ref;
1864         DBRefEntry[] res = DBRefUtils.selectDbRefs(!isProtein(), tmp);
1865         if (res != null && res[0] == tmp[0])
1866         {
1867           primaries.add(ref);
1868           continue;
1869         }
1870       }
1871       return primaries;
1872     }
1873   }
1874
1875   /**
1876    * {@inheritDoc}
1877    */
1878   @Override
1879   public List<SequenceFeature> findFeatures(int fromColumn, int toColumn,
1880           String... types)
1881   {
1882     int startPos = findPosition(fromColumn - 1); // convert base 1 to base 0
1883     int endPos = fromColumn == toColumn ? startPos
1884             : findPosition(toColumn - 1);
1885
1886     List<SequenceFeature> result = getFeatures().findFeatures(startPos,
1887             endPos, types);
1888
1889     /*
1890      * if end column is gapped, endPos may be to the right,
1891      * and we may have included adjacent or enclosing features;
1892      * remove any that are not enclosing, non-contact features
1893      */
1894     boolean endColumnIsGapped = toColumn > 0 && toColumn <= sequence.length
1895             && Comparison.isGap(sequence[toColumn - 1]);
1896     if (endPos > this.end || endColumnIsGapped)
1897     {
1898       ListIterator<SequenceFeature> it = result.listIterator();
1899       while (it.hasNext())
1900       {
1901         SequenceFeature sf = it.next();
1902         int sfBegin = sf.getBegin();
1903         int sfEnd = sf.getEnd();
1904         int featureStartColumn = findIndex(sfBegin);
1905         if (featureStartColumn > toColumn)
1906         {
1907           it.remove();
1908         }
1909         else if (featureStartColumn < fromColumn)
1910         {
1911           int featureEndColumn = sfEnd == sfBegin ? featureStartColumn
1912                   : findIndex(sfEnd);
1913           if (featureEndColumn < fromColumn)
1914           {
1915             it.remove();
1916           }
1917           else if (featureEndColumn > toColumn && sf.isContactFeature())
1918           {
1919             /*
1920              * remove an enclosing feature if it is a contact feature
1921              */
1922             it.remove();
1923           }
1924         }
1925       }
1926     }
1927
1928     return result;
1929   }
1930
1931   /**
1932    * Invalidates any stale cursors (forcing recalculation) by incrementing the
1933    * token that has to match the one presented by the cursor
1934    */
1935   @Override
1936   public void sequenceChanged()
1937   {
1938     changeCount++;
1939   }
1940
1941   /**
1942    * {@inheritDoc}
1943    */
1944   @Override
1945   public int replace(char c1, char c2)
1946   {
1947     if (c1 == c2)
1948     {
1949       return 0;
1950     }
1951     int count = 0;
1952     synchronized (sequence)
1953     {
1954       for (int c = 0; c < sequence.length; c++)
1955       {
1956         if (sequence[c] == c1)
1957         {
1958           sequence[c] = c2;
1959           count++;
1960         }
1961       }
1962     }
1963     if (count > 0)
1964     {
1965       sequenceChanged();
1966     }
1967
1968     return count;
1969   }
1970
1971   @Override
1972   public String getSequenceStringFromIterator(Iterator<int[]> it)
1973   {
1974     StringBuilder newSequence = new StringBuilder();
1975     while (it.hasNext())
1976     {
1977       int[] block = it.next();
1978       if (it.hasNext())
1979       {
1980         newSequence.append(getSequence(block[0], block[1] + 1));
1981       }
1982       else
1983       {
1984         newSequence.append(getSequence(block[0], block[1]));
1985       }
1986     }
1987
1988     return newSequence.toString();
1989   }
1990
1991   @Override
1992   public int firstResidueOutsideIterator(Iterator<int[]> regions)
1993   {
1994     int start = 0;
1995
1996     if (!regions.hasNext())
1997     {
1998       return findIndex(getStart()) - 1;
1999     }
2000
2001     // Simply walk along the sequence whilst watching for region
2002     // boundaries
2003     int hideStart = getLength();
2004     int hideEnd = -1;
2005     boolean foundStart = false;
2006
2007     // step through the non-gapped positions of the sequence
2008     for (int i = getStart(); i <= getEnd() && (!foundStart); i++)
2009     {
2010       // get alignment position of this residue in the sequence
2011       int p = findIndex(i) - 1;
2012
2013       // update region start/end
2014       while (hideEnd < p && regions.hasNext())
2015       {
2016         int[] region = regions.next();
2017         hideStart = region[0];
2018         hideEnd = region[1];
2019       }
2020       if (hideEnd < p)
2021       {
2022         hideStart = getLength();
2023       }
2024       // update boundary for sequence
2025       if (p < hideStart)
2026       {
2027         start = p;
2028         foundStart = true;
2029       }
2030     }
2031
2032     if (foundStart)
2033     {
2034       return start;
2035     }
2036     // otherwise, sequence was completely hidden
2037     return 0;
2038   }
2039 }