src/jalview/datamodel/Mapping.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.9)
   3  * Copyright (C) 2015 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       return new AlignedCodon(alignedCodon[0], alignedCodon[1],
 159               alignedCodon[2], peptide);
 160     }
 161
 162     /**
 163      * Retrieve the translation as the 'mapped to' position in the mapped to
 164      * sequence.
 165      *
 166      * @return
 167      */
 168     private String getPeptide()
 169     {
 170       // TODO should ideally handle toRatio other than 1 as well...
 171       // i.e. code like getNextCodon()
 172       if (toPosition <= currentToRange[1])
 173       {
 174         SequenceI seq = Mapping.this.to;
 175         char pep = seq.getSequence()[toPosition - seq.getStart()];
 176         toPosition++;
 177         return String.valueOf(pep);
 178       }
 179       if (!toRanges.hasNext())
 180       {
 181         throw new NoSuchElementException("Ran out of peptide at position "
 182                 + toPosition);
 183       }
 184       currentToRange = toRanges.next();
 185       toPosition = currentToRange[0];
 186       return getPeptide();
 187     }
 188
 189     /**
 190      * Get the (base 1) dataset positions for the next codon in the mapping.
 191      *
 192      * @throws IncompleteCodonException
 193      *           if less than 3 remaining bases are mapped
 194      */
 195     private int[] getNextCodon()
 196     {
 197       int[] codon = new int[3];
 198       int codonbase = 0;
 199
 200       while (codonbase < 3)
 201       {
 202         if (fromPosition <= currentFromRange[1])
 203         {
 204           /*
 205            * Add next position from the current start-end range
 206            */
 207           codon[codonbase++] = fromPosition++;
 208         }
 209         else
 210         {
 211           /*
 212            * Move to the next range - if there is one
 213            */
 214           if (!fromRanges.hasNext())
 215           {
 216             throw new IncompleteCodonException();
 217           }
 218           currentFromRange = fromRanges.next();
 219           fromPosition = currentFromRange[0];
 220         }
 221       }
 222       return codon;
 223     }
 224
 225     /**
 226      * Get the aligned column positions (base 0) for the given sequence
 227      * positions (base 1), by counting ungapped characters in the aligned
 228      * sequence.
 229      *
 230      * @param codon
 231      * @return
 232      */
 233     private int[] getAlignedCodon(int[] codon)
 234     {
 235       int[] aligned = new int[codon.length];
 236       for (int i = 0; i < codon.length; i++)
 237       {
 238         aligned[i] = getAlignedColumn(codon[i]);
 239       }
 240       return aligned;
 241     }
 242
 243     /**
 244      * Get the aligned column position (base 0) for the given sequence position
 245      * (base 1).
 246      *
 247      * @param sequencePos
 248      * @return
 249      */
 250     private int getAlignedColumn(int sequencePos)
 251     {
 252       /*
 253        * allow for offset e.g. treat pos 8 as 2 if sequence starts at 7
 254        */
 255       int truePos = sequencePos - (start - 1);
 256       while (alignedBases < truePos
 257               && alignedColumn < alignedSeq.length)
 258       {
 259         if (alignedSeq[alignedColumn++] != gap)
 260         {
 261           alignedBases++;
 262         }
 263       }
 264       return alignedColumn - 1;
 265     }
 266
 267     @Override
 268     public void remove()
 269     {
 270       // ignore
 271     }
 272
 273   }
 274
 275   /**
 276    * Contains the start-end pairs mapping from the associated sequence to the
 277    * sequence in the database coordinate system. It also takes care of step
 278    * difference between coordinate systems.
 279    */
 280   MapList map = null;
 281
 282   /**
 283    * The sequence that map maps the associated sequence to (if any).
 284    */
 285   SequenceI to = null;
 286
 287   public Mapping(MapList map)
 288   {
 289     super();
 290     this.map = map;
 291   }
 292
 293   public Mapping(SequenceI to, MapList map)
 294   {
 295     this(map);
 296     this.to = to;
 297   }
 298
 299   /**
 300    * create a new mapping from
 301    *
 302    * @param to
 303    *          the sequence being mapped
 304    * @param exon
 305    *          int[] {start,end,start,end} series on associated sequence
 306    * @param is
 307    *          int[] {start,end,...} ranges on the reference frame being mapped
 308    *          to
 309    * @param i
 310    *          step size on associated sequence
 311    * @param j
 312    *          step size on mapped frame
 313    */
 314   public Mapping(SequenceI to, int[] exon, int[] is, int i, int j)
 315   {
 316     this(to, new MapList(exon, is, i, j));
 317   }
 318
 319   /**
 320    * create a duplicate (and independent) mapping object with the same reference
 321    * to any SequenceI being mapped to.
 322    *
 323    * @param map2
 324    */
 325   public Mapping(Mapping map2)
 326   {
 327     if (map2 != this && map2 != null)
 328     {
 329       if (map2.map != null)
 330       {
 331         map = new MapList(map2.map);
 332       }
 333       to = map2.to;
 334     }
 335   }
 336
 337   /**
 338    * @return the map
 339    */
 340   public MapList getMap()
 341   {
 342     return map;
 343   }
 344
 345   /**
 346    * @param map
 347    *          the map to set
 348    */
 349   public void setMap(MapList map)
 350   {
 351     this.map = map;
 352   }
 353
 354   /**
 355    * Equals that compares both the to references and MapList mappings.
 356    *
 357    * @param other
 358    * @return
 359    */
 360   @Override
 361   public boolean equals(Object o)
 362   {
 363     // TODO should override Object.hashCode() to ensure that equal objects have
 364     // equal hashcodes
 365     if (o == null || !(o instanceof Mapping))
 366     {
 367       return false;
 368     }
 369     Mapping other = (Mapping) o;
 370     if (other == this)
 371     {
 372       return true;
 373     }
 374     if (other.to != to)
 375     {
 376       return false;
 377     }
 378     if ((map != null && other.map == null)
 379             || (map == null && other.map != null))
 380     {
 381       return false;
 382     }
 383     if ((map == null && other.map == null) || map.equals(other.map))
 384     {
 385       return true;
 386     }
 387     return false;
 388   }
 389
 390   /**
 391    * get the 'initial' position in the associated sequence for a position in the
 392    * mapped reference frame
 393    *
 394    * @param mpos
 395    * @return
 396    */
 397   public int getPosition(int mpos)
 398   {
 399     if (map != null)
 400     {
 401       int[] mp = map.shiftTo(mpos);
 402       if (mp != null)
 403       {
 404         return mp[0];
 405       }
 406     }
 407     return mpos;
 408   }
 409
 410   /**
 411    * gets boundary in direction of mapping
 412    *
 413    * @param position
 414    *          in mapped reference frame
 415    * @return int{start, end} positions in associated sequence (in direction of
 416    *         mapped word)
 417    */
 418   public int[] getWord(int mpos)
 419   {
 420     if (map != null)
 421     {
 422       return map.getToWord(mpos);
 423     }
 424     return null;
 425   }
 426
 427   /**
 428    * width of mapped unit in associated sequence
 429    *
 430    */
 431   public int getWidth()
 432   {
 433     if (map != null)
 434     {
 435       return map.getFromRatio();
 436     }
 437     return 1;
 438   }
 439
 440   /**
 441    * width of unit in mapped reference frame
 442    *
 443    * @return
 444    */
 445   public int getMappedWidth()
 446   {
 447     if (map != null)
 448     {
 449       return map.getToRatio();
 450     }
 451     return 1;
 452   }
 453
 454   /**
 455    * get mapped position in the associated reference frame for position pos in
 456    * the associated sequence.
 457    *
 458    * @param pos
 459    * @return
 460    */
 461   public int getMappedPosition(int pos)
 462   {
 463     if (map != null)
 464     {
 465       int[] mp = map.shiftFrom(pos);
 466       if (mp != null)
 467       {
 468         return mp[0];
 469       }
 470     }
 471     return pos;
 472   }
 473
 474   public int[] getMappedWord(int pos)
 475   {
 476     if (map != null)
 477     {
 478       int[] mp = map.shiftFrom(pos);
 479       if (mp != null)
 480       {
 481         return new int[] { mp[0], mp[0] + mp[2] * (map.getToRatio() - 1) };
 482       }
 483     }
 484     return null;
 485   }
 486
 487   /**
 488    * locates the region of feature f in the associated sequence's reference
 489    * frame
 490    *
 491    * @param f
 492    * @return one or more features corresponding to f
 493    */
 494   public SequenceFeature[] locateFeature(SequenceFeature f)
 495   {
 496     if (true)
 497     { // f.getBegin()!=f.getEnd()) {
 498       if (map != null)
 499       {
 500         int[] frange = map.locateInFrom(f.getBegin(), f.getEnd());
 501         if (frange == null)
 502         {
 503           // JBPNote - this isprobably not the right thing to doJBPHack
 504           return null;
 505         }
 506         SequenceFeature[] vf = new SequenceFeature[frange.length / 2];
 507         for (int i = 0, v = 0; i < frange.length; i += 2, v++)
 508         {
 509           vf[v] = new SequenceFeature(f);
 510           vf[v].setBegin(frange[i]);
 511           vf[v].setEnd(frange[i + 1]);
 512           if (frange.length > 2)
 513           {
 514             vf[v].setDescription(f.getDescription() + "\nPart " + (v + 1));
 515           }
 516         }
 517         return vf;
 518       }
 519     }
 520     if (false) // else
 521     {
 522       int[] word = getWord(f.getBegin());
 523       if (word[0] < word[1])
 524       {
 525         f.setBegin(word[0]);
 526       }
 527       else
 528       {
 529         f.setBegin(word[1]);
 530       }
 531       word = getWord(f.getEnd());
 532       if (word[0] > word[1])
 533       {
 534         f.setEnd(word[0]);
 535       }
 536       else
 537       {
 538         f.setEnd(word[1]);
 539       }
 540     }
 541     // give up and just return the feature.
 542     return new SequenceFeature[] { f };
 543   }
 544
 545   /**
 546    * return a series of contigs on the associated sequence corresponding to the
 547    * from,to interval on the mapped reference frame
 548    *
 549    * @param from
 550    * @param to
 551    * @return int[] { from_i, to_i for i=1 to n contiguous regions in the
 552    *         associated sequence}
 553    */
 554   public int[] locateRange(int from, int to)
 555   {
 556     if (map != null)
 557     {
 558       if (from <= to)
 559       {
 560         from = (map.getToLowest() < from) ? from : map.getToLowest();
 561         to = (map.getToHighest() > to) ? to : map.getToHighest();
 562         if (from > to)
 563         {
 564           return null;
 565         }
 566       }
 567       else
 568       {
 569         from = (map.getToHighest() > from) ? from : map.getToHighest();
 570         to = (map.getToLowest() < to) ? to : map.getToLowest();
 571         if (from < to)
 572         {
 573           return null;
 574         }
 575       }
 576       return map.locateInFrom(from, to);
 577     }
 578     return new int[] { from, to };
 579   }
 580
 581   /**
 582    * return a series of mapped contigs mapped from a range on the associated
 583    * sequence
 584    *
 585    * @param from
 586    * @param to
 587    * @return
 588    */
 589   public int[] locateMappedRange(int from, int to)
 590   {
 591     if (map != null)
 592     {
 593
 594       if (from <= to)
 595       {
 596         from = (map.getFromLowest() < from) ? from : map.getFromLowest();
 597         to = (map.getFromHighest() > to) ? to : map.getFromHighest();
 598         if (from > to)
 599         {
 600           return null;
 601         }
 602       }
 603       else
 604       {
 605         from = (map.getFromHighest() > from) ? from : map.getFromHighest();
 606         to = (map.getFromLowest() < to) ? to : map.getFromLowest();
 607         if (from < to)
 608         {
 609           return null;
 610         }
 611       }
 612       return map.locateInTo(from, to);
 613     }
 614     return new int[] { from, to };
 615   }
 616
 617   /**
 618    * return a new mapping object with a maplist modifed to only map the visible
 619    * regions defined by viscontigs.
 620    *
 621    * @param viscontigs
 622    * @return
 623    */
 624   public Mapping intersectVisContigs(int[] viscontigs)
 625   {
 626     Mapping copy = new Mapping(this);
 627     if (map != null)
 628     {
 629       int vpos = 0;
 630       int apos = 0;
 631       Vector toRange = new Vector();
 632       Vector fromRange = new Vector();
 633       for (int vc = 0; vc < viscontigs.length; vc += 2)
 634       {
 635         // find a mapped range in this visible region
 636         int[] mpr = locateMappedRange(1 + viscontigs[vc],
 637                 viscontigs[vc + 1] - 1);
 638         if (mpr != null)
 639         {
 640           for (int m = 0; m < mpr.length; m += 2)
 641           {
 642             toRange.addElement(new int[] { mpr[m], mpr[m + 1] });
 643             int[] xpos = locateRange(mpr[m], mpr[m + 1]);
 644             for (int x = 0; x < xpos.length; x += 2)
 645             {
 646               fromRange.addElement(new int[] { xpos[x], xpos[x + 1] });
 647             }
 648           }
 649         }
 650       }
 651       int[] from = new int[fromRange.size() * 2];
 652       int[] to = new int[toRange.size() * 2];
 653       int[] r;
 654       for (int f = 0, fSize = fromRange.size(); f < fSize; f++)
 655       {
 656         r = (int[]) fromRange.elementAt(f);
 657         from[f * 2] = r[0];
 658         from[f * 2 + 1] = r[1];
 659       }
 660       for (int f = 0, fSize = toRange.size(); f < fSize; f++)
 661       {
 662         r = (int[]) toRange.elementAt(f);
 663         to[f * 2] = r[0];
 664         to[f * 2 + 1] = r[1];
 665       }
 666       copy.setMap(new MapList(from, to, map.getFromRatio(), map
 667               .getToRatio()));
 668     }
 669     return copy;
 670   }
 671
 672   /**
 673    * get the sequence being mapped to - if any
 674    *
 675    * @return null or a dataset sequence
 676    */
 677   public SequenceI getTo()
 678   {
 679     return to;
 680   }
 681
 682   /**
 683    * set the dataset sequence being mapped to if any
 684    *
 685    * @param tto
 686    */
 687   public void setTo(SequenceI tto)
 688   {
 689     to = tto;
 690   }
 691
 692   /*
 693    * (non-Javadoc)
 694    *
 695    * @see java.lang.Object#finalize()
 696    */
 697   protected void finalize() throws Throwable
 698   {
 699     map = null;
 700     to = null;
 701     super.finalize();
 702   }
 703
 704   public Iterator<AlignedCodon> getCodonIterator(SequenceI seq, char gapChar)
 705   {
 706     return new AlignedCodonIterator(seq, gapChar);
 707   }
 708
 709 }