src/jalview/datamodel/Mapping.java

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