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