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