src/jalview/datamodel/Mapping.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.util.MapList;
  24
  25 import java.util.Iterator;
  26 import java.util.NoSuchElementException;
  27 import java.util.Vector;
  28
  29 public class Mapping
  30 {
  31   /**
  32    * An iterator that serves the aligned codon positions (with their protein
  33    * products).
  34    *
  35    * @author gmcarstairs
  36    *
  37    */
  38   public class AlignedCodonIterator implements Iterator<AlignedCodon>
  39   {
  40     /*
  41      * The gap character used in the aligned sequence
  42      */
  43     private final char gap;
  44
  45     /*
  46      * The characters of the aligned sequence e.g. "-cGT-ACgTG-"
  47      */
  48     private final char[] alignedSeq;
  49
  50     /*
  51      * the sequence start residue
  52      */
  53     private int start;
  54
  55     /*
  56      * Next position (base 0) in the aligned sequence
  57      */
  58     private int alignedColumn = 0;
  59
  60     /*
  61      * Count of bases up to and including alignedColumn position
  62      */
  63     private int alignedBases = 0;
  64
  65     /*
  66      * [start, end] from ranges (base 1)
  67      */
  68     private Iterator<int[]> fromRanges;
  69
  70     /*
  71      * [start, end] to ranges (base 1)
  72      */
  73     private Iterator<int[]> toRanges;
  74
  75     /*
  76      * The current [start, end] (base 1) from range
  77      */
  78     private int[] currentFromRange = null;
  79
  80     /*
  81      * The current [start, end] (base 1) to range
  82      */
  83     private int[] currentToRange = null;
  84
  85     /*
  86      * The next 'from' position (base 1) to process
  87      */
  88     private int fromPosition = 0;
  89
  90     /*
  91      * The next 'to' position (base 1) to process
  92      */
  93     private int toPosition = 0;
  94
  95     /**
  96      * Constructor
  97      *
  98      * @param seq
  99      *          the aligned sequence
 100      * @param gapChar
 101      */
 102     public AlignedCodonIterator(SequenceI seq, char gapChar)
 103     {
 104       this.alignedSeq = seq.getSequence();
 105       this.start = seq.getStart();
 106       this.gap = gapChar;
 107       fromRanges = map.getFromRanges().iterator();
 108       toRanges = map.getToRanges().iterator();
 109       if (fromRanges.hasNext())
 110       {
 111         currentFromRange = fromRanges.next();
 112         fromPosition = currentFromRange[0];
 113       }
 114       if (toRanges.hasNext())
 115       {
 116         currentToRange = toRanges.next();
 117         toPosition = currentToRange[0];
 118       }
 119     }
 120
 121     /**
 122      * Returns true unless we have already traversed the whole mapping.
 123      */
 124     @Override
 125     public boolean hasNext()
 126     {
 127       if (fromRanges.hasNext())
 128       {
 129         return true;
 130       }
 131       if (currentFromRange == null || fromPosition >= currentFromRange[1])
 132       {
 133         return false;
 134       }
 135       return true;
 136     }
 137
 138     /**
 139      * Returns the next codon's aligned positions, and translated value.
 140      *
 141      * @throws NoSuchElementException
 142      *           if hasNext() would have returned false
 143      * @throws IncompleteCodonException
 144      *           if not enough mapped bases are left to make up a codon
 145      */
 146     @Override
 147     public AlignedCodon next() throws IncompleteCodonException
 148     {
 149       if (!hasNext())
 150       {
 151         throw new NoSuchElementException();
 152       }
 153
 154       int[] codon = getNextCodon();
 155       int[] alignedCodon = getAlignedCodon(codon);
 156
 157       String peptide = getPeptide();
 158       int peptideCol = toPosition - 1 - Mapping.this.to.getStart();
 159       return new AlignedCodon(alignedCodon[0], alignedCodon[1],
 160               alignedCodon[2], peptide, peptideCol);
 161     }
 162
 163     /**
 164      * Retrieve the translation as the 'mapped to' position in the mapped to
 165      * sequence.
 166      *
 167      * @return
 168      * @throws NoSuchElementException
 169      *           if the 'toRange' is exhausted (nothing to map to)
 170      */
 171     private String getPeptide()
 172     {
 173       // TODO should ideally handle toRatio other than 1 as well...
 174       // i.e. code like getNextCodon()
 175       if (toPosition <= currentToRange[1])
 176       {
 177         SequenceI seq = Mapping.this.to;
 178         char pep = seq.getSequence()[toPosition - seq.getStart()];
 179         toPosition++;
 180         return String.valueOf(pep);
 181       }
 182       if (!toRanges.hasNext())
 183       {
 184         throw new NoSuchElementException("Ran out of peptide at position "
 185                 + toPosition);
 186       }
 187       currentToRange = toRanges.next();
 188       toPosition = currentToRange[0];
 189       return getPeptide();
 190     }
 191
 192     /**
 193      * Get the (base 1) dataset positions for the next codon in the mapping.
 194      *
 195      * @throws IncompleteCodonException
 196      *           if less than 3 remaining bases are mapped
 197      */
 198     private int[] getNextCodon()
 199     {
 200       int[] codon = new int[3];
 201       int codonbase = 0;
 202
 203       while (codonbase < 3)
 204       {
 205         if (fromPosition <= currentFromRange[1])
 206         {
 207           /*
 208            * Add next position from the current start-end range
 209            */
 210           codon[codonbase++] = fromPosition++;
 211         }
 212         else
 213         {
 214           /*
 215            * Move to the next range - if there is one
 216            */
 217           if (!fromRanges.hasNext())
 218           {
 219             throw new IncompleteCodonException();
 220           }
 221           currentFromRange = fromRanges.next();
 222           fromPosition = currentFromRange[0];
 223         }
 224       }
 225       return codon;
 226     }
 227
 228     /**
 229      * Get the aligned column positions (base 0) for the given sequence
 230      * positions (base 1), by counting ungapped characters in the aligned
 231      * sequence.
 232      *
 233      * @param codon
 234      * @return
 235      */
 236     private int[] getAlignedCodon(int[] codon)
 237     {
 238       int[] aligned = new int[codon.length];
 239       for (int i = 0; i < codon.length; i++)
 240       {
 241         aligned[i] = getAlignedColumn(codon[i]);
 242       }
 243       return aligned;
 244     }
 245
 246     /**
 247      * Get the aligned column position (base 0) for the given sequence position
 248      * (base 1).
 249      *
 250      * @param sequencePos
 251      * @return
 252      */
 253     private int getAlignedColumn(int sequencePos)
 254     {
 255       /*
 256        * allow for offset e.g. treat pos 8 as 2 if sequence starts at 7
 257        */
 258       int truePos = sequencePos - (start - 1);
 259       while (alignedBases < truePos && alignedColumn < alignedSeq.length)
 260       {
 261         if (alignedSeq[alignedColumn++] != gap)
 262         {
 263           alignedBases++;
 264         }
 265       }
 266       return alignedColumn - 1;
 267     }
 268
 269     @Override
 270     public void remove()
 271     {
 272       // ignore
 273     }
 274
 275   }
 276
 277   /*
 278    * Contains the start-end pairs mapping from the associated sequence to the
 279    * sequence in the database coordinate system. It also takes care of step
 280    * difference between coordinate systems.
 281    */
 282   MapList map = null;
 283
 284   /*
 285    * The sequence that map maps the associated sequence to (if any).
 286    */
 287   SequenceI to = null;
 288
 289   /*
 290    * optional sequence id for the 'from' ranges
 291    */
 292   private String mappedFromId;
 293
 294   public Mapping(MapList map)
 295   {
 296     super();
 297     this.map = map;
 298   }
 299
 300   public Mapping(SequenceI to, MapList map)
 301   {
 302     this(map);
 303     this.to = to;
 304   }
 305
 306   /**
 307    * create a new mapping from
 308    *
 309    * @param to
 310    *          the sequence being mapped
 311    * @param exon
 312    *          int[] {start,end,start,end} series on associated sequence
 313    * @param is
 314    *          int[] {start,end,...} ranges on the reference frame being mapped
 315    *          to
 316    * @param i
 317    *          step size on associated sequence
 318    * @param j
 319    *          step size on mapped frame
 320    */
 321   public Mapping(SequenceI to, int[] exon, int[] is, int i, int j)
 322   {
 323     this(to, new MapList(exon, is, i, j));
 324   }
 325
 326   /**
 327    * create a duplicate (and independent) mapping object with the same reference
 328    * to any SequenceI being mapped to.
 329    *
 330    * @param map2
 331    */
 332   public Mapping(Mapping map2)
 333   {
 334     if (map2 != this && map2 != null)
 335     {
 336       if (map2.map != null)
 337       {
 338         map = new MapList(map2.map);
 339       }
 340       to = map2.to;
 341       mappedFromId = map2.mappedFromId;
 342     }
 343   }
 344
 345   /**
 346    * @return the map
 347    */
 348   public MapList getMap()
 349   {
 350     return map;
 351   }
 352
 353   /**
 354    * @param map
 355    *          the map to set
 356    */
 357   public void setMap(MapList map)
 358   {
 359     this.map = map;
 360   }
 361
 362   /**
 363    * Equals that compares both the to references and MapList mappings.
 364    *
 365    * @param o
 366    * @return
 367    * @see MapList#equals
 368    */
 369   @Override
 370   public boolean equals(Object o)
 371   {
 372     if (o == null || !(o instanceof Mapping))
 373     {
 374       return false;
 375     }
 376     Mapping other = (Mapping) o;
 377     if (other == this)
 378     {
 379       return true;
 380     }
 381     if (other.to != to)
 382     {
 383       return false;
 384     }
 385     if ((map != null && other.map == null)
 386             || (map == null && other.map != null))
 387     {
 388       return false;
 389     }
 390     if ((map == null && other.map == null) || map.equals(other.map))
 391     {
 392       return true;
 393     }
 394     return false;
 395   }
 396
 397   /**
 398    * Returns a hashCode made from the sequence and maplist
 399    */
 400   @Override
 401   public int hashCode()
 402   {
 403     int hashCode = (this.to == null ? 1 : this.to.hashCode());
 404     if (this.map != null)
 405     {
 406       hashCode = hashCode * 31 + this.map.hashCode();
 407     }
 408
 409     return hashCode;
 410   }
 411
 412   /**
 413    * get the 'initial' position in the associated sequence for a position in the
 414    * mapped reference frame
 415    *
 416    * @param mpos
 417    * @return
 418    */
 419   public int getPosition(int mpos)
 420   {
 421     if (map != null)
 422     {
 423       int[] mp = map.shiftTo(mpos);
 424       if (mp != null)
 425       {
 426         return mp[0];
 427       }
 428     }
 429     return mpos;
 430   }
 431
 432   /**
 433    * gets boundary in direction of mapping
 434    *
 435    * @param position
 436    *          in mapped reference frame
 437    * @return int{start, end} positions in associated sequence (in direction of
 438    *         mapped word)
 439    */
 440   public int[] getWord(int mpos)
 441   {
 442     if (map != null)
 443     {
 444       return map.getToWord(mpos);
 445     }
 446     return null;
 447   }
 448
 449   /**
 450    * width of mapped unit in associated sequence
 451    *
 452    */
 453   public int getWidth()
 454   {
 455     if (map != null)
 456     {
 457       return map.getFromRatio();
 458     }
 459     return 1;
 460   }
 461
 462   /**
 463    * width of unit in mapped reference frame
 464    *
 465    * @return
 466    */
 467   public int getMappedWidth()
 468   {
 469     if (map != null)
 470     {
 471       return map.getToRatio();
 472     }
 473     return 1;
 474   }
 475
 476   /**
 477    * get mapped position in the associated reference frame for position pos in
 478    * the associated sequence.
 479    *
 480    * @param pos
 481    * @return
 482    */
 483   public int getMappedPosition(int pos)
 484   {
 485     if (map != null)
 486     {
 487       int[] mp = map.shiftFrom(pos);
 488       if (mp != null)
 489       {
 490         return mp[0];
 491       }
 492     }
 493     return pos;
 494   }
 495
 496   public int[] getMappedWord(int pos)
 497   {
 498     if (map != null)
 499     {
 500       int[] mp = map.shiftFrom(pos);
 501       if (mp != null)
 502       {
 503         return new int[] { mp[0], mp[0] + mp[2] * (map.getToRatio() - 1) };
 504       }
 505     }
 506     return null;
 507   }
 508
 509   /**
 510    * locates the region of feature f in the associated sequence's reference
 511    * frame
 512    *
 513    * @param f
 514    * @return one or more features corresponding to f
 515    */
 516   public SequenceFeature[] locateFeature(SequenceFeature f)
 517   {
 518     if (true)
 519     { // f.getBegin()!=f.getEnd()) {
 520       if (map != null)
 521       {
 522         int[] frange = map.locateInFrom(f.getBegin(), f.getEnd());
 523         if (frange == null)
 524         {
 525           // JBPNote - this isprobably not the right thing to doJBPHack
 526           return null;
 527         }
 528         SequenceFeature[] vf = new SequenceFeature[frange.length / 2];
 529         for (int i = 0, v = 0; i < frange.length; i += 2, v++)
 530         {
 531           vf[v] = new SequenceFeature(f);
 532           vf[v].setBegin(frange[i]);
 533           vf[v].setEnd(frange[i + 1]);
 534           if (frange.length > 2)
 535           {
 536             vf[v].setDescription(f.getDescription() + "\nPart " + (v + 1));
 537           }
 538         }
 539         return vf;
 540       }
 541     }
 542     if (false) // else
 543     {
 544       int[] word = getWord(f.getBegin());
 545       if (word[0] < word[1])
 546       {
 547         f.setBegin(word[0]);
 548       }
 549       else
 550       {
 551         f.setBegin(word[1]);
 552       }
 553       word = getWord(f.getEnd());
 554       if (word[0] > word[1])
 555       {
 556         f.setEnd(word[0]);
 557       }
 558       else
 559       {
 560         f.setEnd(word[1]);
 561       }
 562     }
 563     // give up and just return the feature.
 564     return new SequenceFeature[] { f };
 565   }
 566
 567   /**
 568    * return a series of contigs on the associated sequence corresponding to the
 569    * from,to interval on the mapped reference frame
 570    *
 571    * @param from
 572    * @param to
 573    * @return int[] { from_i, to_i for i=1 to n contiguous regions in the
 574    *         associated sequence}
 575    */
 576   public int[] locateRange(int from, int to)
 577   {
 578     if (map != null)
 579     {
 580       if (from <= to)
 581       {
 582         from = (map.getToLowest() < from) ? from : map.getToLowest();
 583         to = (map.getToHighest() > to) ? to : map.getToHighest();
 584         if (from > to)
 585         {
 586           return null;
 587         }
 588       }
 589       else
 590       {
 591         from = (map.getToHighest() > from) ? from : map.getToHighest();
 592         to = (map.getToLowest() < to) ? to : map.getToLowest();
 593         if (from < to)
 594         {
 595           return null;
 596         }
 597       }
 598       return map.locateInFrom(from, to);
 599     }
 600     return new int[] { from, to };
 601   }
 602
 603   /**
 604    * return a series of mapped contigs mapped from a range on the associated
 605    * sequence
 606    *
 607    * @param from
 608    * @param to
 609    * @return
 610    */
 611   public int[] locateMappedRange(int from, int to)
 612   {
 613     if (map != null)
 614     {
 615
 616       if (from <= to)
 617       {
 618         from = (map.getFromLowest() < from) ? from : map.getFromLowest();
 619         to = (map.getFromHighest() > to) ? to : map.getFromHighest();
 620         if (from > to)
 621         {
 622           return null;
 623         }
 624       }
 625       else
 626       {
 627         from = (map.getFromHighest() > from) ? from : map.getFromHighest();
 628         to = (map.getFromLowest() < to) ? to : map.getFromLowest();
 629         if (from < to)
 630         {
 631           return null;
 632         }
 633       }
 634       return map.locateInTo(from, to);
 635     }
 636     return new int[] { from, to };
 637   }
 638
 639   /**
 640    * return a new mapping object with a maplist modifed to only map the visible
 641    * regions defined by viscontigs.
 642    *
 643    * @param viscontigs
 644    * @return
 645    */
 646   public Mapping intersectVisContigs(int[] viscontigs)
 647   {
 648     Mapping copy = new Mapping(this);
 649     if (map != null)
 650     {
 651       int vpos = 0;
 652       int apos = 0;
 653       Vector toRange = new Vector();
 654       Vector fromRange = new Vector();
 655       for (int vc = 0; vc < viscontigs.length; vc += 2)
 656       {
 657         // find a mapped range in this visible region
 658         int[] mpr = locateMappedRange(1 + viscontigs[vc],
 659                 viscontigs[vc + 1] - 1);
 660         if (mpr != null)
 661         {
 662           for (int m = 0; m < mpr.length; m += 2)
 663           {
 664             toRange.addElement(new int[] { mpr[m], mpr[m + 1] });
 665             int[] xpos = locateRange(mpr[m], mpr[m + 1]);
 666             for (int x = 0; x < xpos.length; x += 2)
 667             {
 668               fromRange.addElement(new int[] { xpos[x], xpos[x + 1] });
 669             }
 670           }
 671         }
 672       }
 673       int[] from = new int[fromRange.size() * 2];
 674       int[] to = new int[toRange.size() * 2];
 675       int[] r;
 676       for (int f = 0, fSize = fromRange.size(); f < fSize; f++)
 677       {
 678         r = (int[]) fromRange.elementAt(f);
 679         from[f * 2] = r[0];
 680         from[f * 2 + 1] = r[1];
 681       }
 682       for (int f = 0, fSize = toRange.size(); f < fSize; f++)
 683       {
 684         r = (int[]) toRange.elementAt(f);
 685         to[f * 2] = r[0];
 686         to[f * 2 + 1] = r[1];
 687       }
 688       copy.setMap(new MapList(from, to, map.getFromRatio(), map
 689               .getToRatio()));
 690     }
 691     return copy;
 692   }
 693
 694   /**
 695    * get the sequence being mapped to - if any
 696    *
 697    * @return null or a dataset sequence
 698    */
 699   public SequenceI getTo()
 700   {
 701     return to;
 702   }
 703
 704   /**
 705    * set the dataset sequence being mapped to if any
 706    *
 707    * @param tto
 708    */
 709   public void setTo(SequenceI tto)
 710   {
 711     to = tto;
 712   }
 713
 714   /*
 715    * (non-Javadoc)
 716    *
 717    * @see java.lang.Object#finalize()
 718    */
 719   @Override
 720   protected void finalize() throws Throwable
 721   {
 722     map = null;
 723     to = null;
 724     super.finalize();
 725   }
 726
 727   /**
 728    * Returns an iterator which can serve up the aligned codon column positions
 729    * and their corresponding peptide products
 730    *
 731    * @param seq
 732    *          an aligned (i.e. possibly gapped) sequence
 733    * @param gapChar
 734    * @return
 735    */
 736   public Iterator<AlignedCodon> getCodonIterator(SequenceI seq, char gapChar)
 737   {
 738     return new AlignedCodonIterator(seq, gapChar);
 739   }
 740
 741   /**
 742    * Readable representation for debugging only, not guaranteed not to change
 743    */
 744   @Override
 745   public String toString()
 746   {
 747     return String.format("%s %s", this.map.toString(), this.to == null ? ""
 748             : this.to.getName());
 749   }
 750
 751   /**
 752    * Returns the identifier for the 'from' range sequence, or null if not set
 753    *
 754    * @return
 755    */
 756   public String getMappedFromId()
 757   {
 758     return mappedFromId;
 759   }
 760
 761   /**
 762    * Sets the identifier for the 'from' range sequence
 763    */
 764   public void setMappedFromId(String mappedFromId)
 765   {
 766     this.mappedFromId = mappedFromId;
 767   }
 768
 769 }