X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FAlignmentUtils.java;h=55efaa51c71d83467b20609ef0284ffe96463d34;hb=9b85e1552fa57f02cf6cd312cfbd7efdfd079ea3;hp=450ae2752673431fb19728c540452fe71c626139;hpb=b2cedc8371f6624859f107581e6d84e841d4114b;p=jalview.git diff --git a/src/jalview/analysis/AlignmentUtils.java b/src/jalview/analysis/AlignmentUtils.java index 450ae27..55efaa5 100644 --- a/src/jalview/analysis/AlignmentUtils.java +++ b/src/jalview/analysis/AlignmentUtils.java @@ -20,34 +20,40 @@ */ package jalview.analysis; +import static jalview.io.gff.GffConstants.CLINICAL_SIGNIFICANCE; + +import jalview.commands.RemoveGapColCommand; import jalview.datamodel.AlignedCodon; import jalview.datamodel.AlignedCodonFrame; +import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping; import jalview.datamodel.Alignment; import jalview.datamodel.AlignmentAnnotation; import jalview.datamodel.AlignmentI; import jalview.datamodel.DBRefEntry; -import jalview.datamodel.DBRefSource; -import jalview.datamodel.FeatureProperties; +import jalview.datamodel.GeneLociI; import jalview.datamodel.IncompleteCodonException; import jalview.datamodel.Mapping; -import jalview.datamodel.SearchResults; import jalview.datamodel.Sequence; import jalview.datamodel.SequenceFeature; import jalview.datamodel.SequenceGroup; import jalview.datamodel.SequenceI; -import jalview.io.gff.SequenceOntologyFactory; +import jalview.datamodel.features.SequenceFeatures; +import jalview.io.gff.Gff3Helper; import jalview.io.gff.SequenceOntologyI; import jalview.schemes.ResidueProperties; import jalview.util.Comparison; import jalview.util.DBRefUtils; +import jalview.util.IntRangeComparator; import jalview.util.MapList; import jalview.util.MappingUtils; +import jalview.util.StringUtils; +import java.io.UnsupportedEncodingException; +import java.net.URLEncoder; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; -import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; @@ -57,6 +63,7 @@ import java.util.Map; import java.util.Map.Entry; import java.util.NoSuchElementException; import java.util.Set; +import java.util.SortedMap; import java.util.TreeMap; /** @@ -68,6 +75,52 @@ import java.util.TreeMap; */ public class AlignmentUtils { + private static final int CODON_LENGTH = 3; + + private static final String SEQUENCE_VARIANT = "sequence_variant:"; + + /* + * the 'id' attribute is provided for variant features fetched from + * Ensembl using its REST service with JSON format + */ + public static final String VARIANT_ID = "id"; + + /** + * A data model to hold the 'normal' base value at a position, and an optional + * sequence variant feature + */ + static final class DnaVariant + { + final String base; + + SequenceFeature variant; + + DnaVariant(String nuc) + { + base = nuc; + variant = null; + } + + DnaVariant(String nuc, SequenceFeature var) + { + base = nuc; + variant = var; + } + + public String getSource() + { + return variant == null ? null : variant.getFeatureGroup(); + } + + /** + * toString for aid in the debugger only + */ + @Override + public String toString() + { + return base + ":" + (variant == null ? "" : variant.getDescription()); + } + } /** * given an existing alignment, create a new alignment including all, or up to @@ -79,7 +132,7 @@ public class AlignmentUtils */ public static AlignmentI expandContext(AlignmentI core, int flankSize) { - List sq = new ArrayList(); + List sq = new ArrayList<>(); int maxoffset = 0; for (SequenceI s : core.getSequences()) { @@ -132,10 +185,12 @@ public class AlignmentUtils } } // TODO use Character.toLowerCase to avoid creating String objects? - char[] upstream = new String(ds.getSequence(s.getStart() - 1 - - ustream_ds, s.getStart() - 1)).toLowerCase().toCharArray(); - char[] downstream = new String(ds.getSequence(s_end - 1, s_end - + dstream_ds)).toLowerCase().toCharArray(); + char[] upstream = new String(ds + .getSequence(s.getStart() - 1 - ustream_ds, s.getStart() - 1)) + .toLowerCase().toCharArray(); + char[] downstream = new String( + ds.getSequence(s_end - 1, s_end + dstream_ds)).toLowerCase() + .toCharArray(); char[] coreseq = s.getSequence(); char[] nseq = new char[offset + upstream.length + downstream.length + coreseq.length]; @@ -150,8 +205,8 @@ public class AlignmentUtils System.arraycopy(upstream, 0, nseq, p, upstream.length); System.arraycopy(coreseq, 0, nseq, p + upstream.length, coreseq.length); - System.arraycopy(downstream, 0, nseq, p + coreseq.length - + upstream.length, downstream.length); + System.arraycopy(downstream, 0, nseq, + p + coreseq.length + upstream.length, downstream.length); s.setSequence(new String(nseq)); s.setStart(s.getStart() - ustream_ds); s.setEnd(s_end + downstream.length); @@ -207,7 +262,7 @@ public class AlignmentUtils public static Map> getSequencesByName( AlignmentI al) { - Map> theMap = new LinkedHashMap>(); + Map> theMap = new LinkedHashMap<>(); for (SequenceI seq : al.getSequences()) { String name = seq.getName(); @@ -216,7 +271,7 @@ public class AlignmentUtils List seqs = theMap.get(name); if (seqs == null) { - seqs = new ArrayList(); + seqs = new ArrayList<>(); theMap.put(name, seqs); } seqs.add(seq); @@ -243,8 +298,8 @@ public class AlignmentUtils return false; } - Set mappedDna = new HashSet(); - Set mappedProtein = new HashSet(); + Set mappedDna = new HashSet<>(); + Set mappedProtein = new HashSet<>(); /* * First pass - map sequences where cross-references exist. This include @@ -278,9 +333,9 @@ public class AlignmentUtils * @return */ protected static boolean mapProteinToCdna( - final AlignmentI proteinAlignment, - final AlignmentI cdnaAlignment, Set mappedDna, - Set mappedProtein, boolean xrefsOnly) + final AlignmentI proteinAlignment, final AlignmentI cdnaAlignment, + Set mappedDna, Set mappedProtein, + boolean xrefsOnly) { boolean mappingExistsOrAdded = false; List thisSeqs = proteinAlignment.getSequences(); @@ -309,9 +364,8 @@ public class AlignmentUtils * Don't map non-xrefd sequences more than once each. This heuristic * allows us to pair up similar sequences in ordered alignments. */ - if (!xrefsOnly - && (mappedProtein.contains(aaSeq) || mappedDna - .contains(cdnaSeq))) + if (!xrefsOnly && (mappedProtein.contains(aaSeq) + || mappedDna.contains(cdnaSeq))) { continue; } @@ -322,7 +376,7 @@ public class AlignmentUtils } else { - MapList map = mapProteinSequenceToCdna(aaSeq, cdnaSeq); + MapList map = mapCdnaToProtein(aaSeq, cdnaSeq); if (map != null) { acf.addMap(cdnaSeq, aaSeq, map); @@ -345,7 +399,7 @@ public class AlignmentUtils * Answers true if the mappings include one between the given (dataset) * sequences. */ - public static boolean mappingExists(List mappings, + protected static boolean mappingExists(List mappings, SequenceI aaSeq, SequenceI cdnaSeq) { if (mappings != null) @@ -362,16 +416,23 @@ public class AlignmentUtils } /** - * Build a mapping (if possible) of a protein to a cDNA sequence. The cDNA - * must be three times the length of the protein, possibly after ignoring - * start and/or stop codons, and must translate to the protein. Returns null - * if no mapping is determined. + * Builds a mapping (if possible) of a cDNA to a protein sequence. + *
    + *
  • first checks if the cdna translates exactly to the protein + * sequence
    • + *
  • else checks for translation after removing a STOP codon
    • + *
  • else checks for translation after removing a START codon
    • + *
  • if that fails, inspect CDS features on the cDNA sequence
    • + *
+ * Returns null if no mapping is determined. * - * @param proteinSeqs + * @param proteinSeq + * the aligned protein sequence * @param cdnaSeq + * the aligned cdna sequence * @return */ - public static MapList mapProteinSequenceToCdna(SequenceI proteinSeq, + public static MapList mapCdnaToProtein(SequenceI proteinSeq, SequenceI cdnaSeq) { /* @@ -380,8 +441,9 @@ public class AlignmentUtils * String objects. */ final SequenceI proteinDataset = proteinSeq.getDatasetSequence(); - char[] aaSeqChars = proteinDataset != null ? proteinDataset - .getSequence() : proteinSeq.getSequence(); + char[] aaSeqChars = proteinDataset != null + ? proteinDataset.getSequence() + : proteinSeq.getSequence(); final SequenceI cdnaDataset = cdnaSeq.getDatasetSequence(); char[] cdnaSeqChars = cdnaDataset != null ? cdnaDataset.getSequence() : cdnaSeq.getSequence(); @@ -393,7 +455,7 @@ public class AlignmentUtils /* * cdnaStart/End, proteinStartEnd are base 1 (for dataset sequence mapping) */ - final int mappedLength = 3 * aaSeqChars.length; + final int mappedLength = CODON_LENGTH * aaSeqChars.length; int cdnaLength = cdnaSeqChars.length; int cdnaStart = cdnaSeq.getStart(); int cdnaEnd = cdnaSeq.getEnd(); @@ -401,18 +463,18 @@ public class AlignmentUtils final int proteinEnd = proteinSeq.getEnd(); /* - * If lengths don't match, try ignoring stop codon. + * If lengths don't match, try ignoring stop codon (if present) */ if (cdnaLength != mappedLength && cdnaLength > 2) { - String lastCodon = String.valueOf(cdnaSeqChars, cdnaLength - 3, 3) - .toUpperCase(); - for (String stop : ResidueProperties.STOP) + String lastCodon = String.valueOf(cdnaSeqChars, + cdnaLength - CODON_LENGTH, CODON_LENGTH).toUpperCase(); + for (String stop : ResidueProperties.STOP_CODONS) { if (lastCodon.equals(stop)) { - cdnaEnd -= 3; - cdnaLength -= 3; + cdnaEnd -= CODON_LENGTH; + cdnaLength -= CODON_LENGTH; break; } } @@ -422,27 +484,30 @@ public class AlignmentUtils * If lengths still don't match, try ignoring start codon. */ int startOffset = 0; - if (cdnaLength != mappedLength - && cdnaLength > 2 - && String.valueOf(cdnaSeqChars, 0, 3).toUpperCase() + if (cdnaLength != mappedLength && cdnaLength > 2 + && String.valueOf(cdnaSeqChars, 0, CODON_LENGTH).toUpperCase() .equals(ResidueProperties.START)) { - startOffset += 3; - cdnaStart += 3; - cdnaLength -= 3; + startOffset += CODON_LENGTH; + cdnaStart += CODON_LENGTH; + cdnaLength -= CODON_LENGTH; } - if (cdnaLength != mappedLength) - { - return null; - } - if (!translatesAs(cdnaSeqChars, startOffset, aaSeqChars)) + if (translatesAs(cdnaSeqChars, startOffset, aaSeqChars)) { - return null; + /* + * protein is translation of dna (+/- start/stop codons) + */ + MapList map = new MapList(new int[] { cdnaStart, cdnaEnd }, + new int[] + { proteinStart, proteinEnd }, CODON_LENGTH, 1); + return map; } - MapList map = new MapList(new int[] { cdnaStart, cdnaEnd }, new int[] { - proteinStart, proteinEnd }, 3, 1); - return map; + + /* + * translation failed - try mapping CDS annotated regions of dna + */ + return mapCdsToProtein(cdnaSeq, proteinSeq); } /** @@ -463,17 +528,20 @@ public class AlignmentUtils return false; } - int aaResidue = 0; - for (int i = cdnaStart; i < cdnaSeqChars.length - 2 - && aaResidue < aaSeqChars.length; i += 3, aaResidue++) + int aaPos = 0; + int dnaPos = cdnaStart; + for (; dnaPos < cdnaSeqChars.length - 2 + && aaPos < aaSeqChars.length; dnaPos += CODON_LENGTH, aaPos++) { - String codon = String.valueOf(cdnaSeqChars, i, 3); + String codon = String.valueOf(cdnaSeqChars, dnaPos, CODON_LENGTH); final String translated = ResidueProperties.codonTranslate(codon); + /* * allow * in protein to match untranslatable in dna */ - final char aaRes = aaSeqChars[aaResidue]; - if ((translated == null || "STOP".equals(translated)) && aaRes == '*') + final char aaRes = aaSeqChars[aaPos]; + if ((translated == null || ResidueProperties.STOP.equals(translated)) + && aaRes == '*') { continue; } @@ -485,8 +553,33 @@ public class AlignmentUtils return false; } } - // fail if we didn't match all of the aa sequence - return (aaResidue == aaSeqChars.length); + + /* + * check we matched all of the protein sequence + */ + if (aaPos != aaSeqChars.length) + { + return false; + } + + /* + * check we matched all of the dna except + * for optional trailing STOP codon + */ + if (dnaPos == cdnaSeqChars.length) + { + return true; + } + if (dnaPos == cdnaSeqChars.length - CODON_LENGTH) + { + String codon = String.valueOf(cdnaSeqChars, dnaPos, CODON_LENGTH); + if (ResidueProperties.STOP + .equals(ResidueProperties.codonTranslate(codon))) + { + return true; + } + } + return false; } /** @@ -528,7 +621,7 @@ public class AlignmentUtils AlignedCodonFrame mapping = null; for (AlignedCodonFrame mp : mappings) { - alignFrom = mp.findAlignedSequence(seq.getDatasetSequence(), al); + alignFrom = mp.findAlignedSequence(seq, al); if (alignFrom != null) { mapping = mp; @@ -559,10 +652,9 @@ public class AlignmentUtils * @param preserveUnmappedGaps * @param preserveMappedGaps */ - public static void alignSequenceAs(SequenceI alignTo, - SequenceI alignFrom, AlignedCodonFrame mapping, String myGap, - char sourceGap, boolean preserveMappedGaps, - boolean preserveUnmappedGaps) + public static void alignSequenceAs(SequenceI alignTo, SequenceI alignFrom, + AlignedCodonFrame mapping, String myGap, char sourceGap, + boolean preserveMappedGaps, boolean preserveUnmappedGaps) { // TODO generalise to work for Protein-Protein, dna-dna, dna-protein @@ -578,15 +670,16 @@ public class AlignmentUtils int toOffset = alignTo.getStart() - 1; int sourceGapMappedLength = 0; boolean inExon = false; - final char[] thisSeq = alignTo.getSequence(); - final char[] thatAligned = alignFrom.getSequence(); - StringBuilder thisAligned = new StringBuilder(2 * thisSeq.length); + final int toLength = alignTo.getLength(); + final int fromLength = alignFrom.getLength(); + StringBuilder thisAligned = new StringBuilder(2 * toLength); /* * Traverse the 'model' aligned sequence */ - for (char sourceChar : thatAligned) + for (int i = 0; i < fromLength; i++) { + char sourceChar = alignFrom.getCharAt(i); if (sourceChar == sourceGap) { sourceGapMappedLength += ratio; @@ -626,9 +719,9 @@ public class AlignmentUtils */ int intronLength = 0; while (basesWritten + toOffset < mappedCodonEnd - && thisSeqPos < thisSeq.length) + && thisSeqPos < toLength) { - final char c = thisSeq[thisSeqPos++]; + final char c = alignTo.getCharAt(thisSeqPos++); if (c != myGapChar) { basesWritten++; @@ -654,7 +747,7 @@ public class AlignmentUtils int gapsToAdd = calculateGapsToInsert(preserveMappedGaps, preserveUnmappedGaps, sourceGapMappedLength, inExon, trailingCopiedGap.length(), intronLength, startOfCodon); - for (int i = 0; i < gapsToAdd; i++) + for (int k = 0; k < gapsToAdd; k++) { thisAligned.append(myGapChar); } @@ -682,9 +775,9 @@ public class AlignmentUtils * At end of model aligned sequence. Copy any remaining target sequence, optionally * including (intron) gaps. */ - while (thisSeqPos < thisSeq.length) + while (thisSeqPos < toLength) { - final char c = thisSeq[thisSeqPos++]; + final char c = alignTo.getCharAt(thisSeqPos++); if (c != myGapChar || preserveUnmappedGaps) { thisAligned.append(c); @@ -757,8 +850,9 @@ public class AlignmentUtils } else { - gapsToAdd = Math.min(intronLength + trailingGapLength - - sourceGapMappedLength, trailingGapLength); + gapsToAdd = Math.min( + intronLength + trailingGapLength - sourceGapMappedLength, + trailingGapLength); } } } @@ -777,163 +871,199 @@ public class AlignmentUtils } /** - * Returns a list of sequences mapped from the given sequences and aligned - * (gapped) in the same way. For example, the cDNA for aligned protein, where - * a single gap in protein generates three gaps in cDNA. + * Realigns the given protein to match the alignment of the dna, using codon + * mappings to translate aligned codon positions to protein residues. * - * @param sequences - * @param gapCharacter - * @param mappings - * @return + * @param protein + * the alignment whose sequences are realigned by this method + * @param dna + * the dna alignment whose alignment we are 'copying' + * @return the number of sequences that were realigned */ - public static List getAlignedTranslation( - List sequences, char gapCharacter, - Set mappings) + public static int alignProteinAsDna(AlignmentI protein, AlignmentI dna) { - List alignedSeqs = new ArrayList(); - - for (SequenceI seq : sequences) + if (protein.isNucleotide() || !dna.isNucleotide()) { - List mapped = getAlignedTranslation(seq, gapCharacter, - mappings); - alignedSeqs.addAll(mapped); + System.err.println("Wrong alignment type in alignProteinAsDna"); + return 0; } - return alignedSeqs; + List unmappedProtein = new ArrayList<>(); + Map> alignedCodons = buildCodonColumnsMap( + protein, dna, unmappedProtein); + return alignProteinAs(protein, alignedCodons, unmappedProtein); } /** - * Returns sequences aligned 'like' the source sequence, as mapped by the - * given mappings. Normally we expect zero or one 'mapped' sequences, but this - * will support 1-to-many as well. + * Realigns the given dna to match the alignment of the protein, using codon + * mappings to translate aligned peptide positions to codons. * - * @param seq - * @param gapCharacter - * @param mappings - * @return + * Always produces a padded CDS alignment. + * + * @param dna + * the alignment whose sequences are realigned by this method + * @param protein + * the protein alignment whose alignment we are 'copying' + * @return the number of sequences that were realigned */ - protected static List getAlignedTranslation(SequenceI seq, - char gapCharacter, Set mappings) + public static int alignCdsAsProtein(AlignmentI dna, AlignmentI protein) { - List result = new ArrayList(); - for (AlignedCodonFrame mapping : mappings) + if (protein.isNucleotide() || !dna.isNucleotide()) + { + System.err.println("Wrong alignment type in alignProteinAsDna"); + return 0; + } + // todo: implement this + List mappings = protein.getCodonFrames(); + int alignedCount = 0; + int width = 0; // alignment width for padding CDS + for (SequenceI dnaSeq : dna.getSequences()) { - if (mapping.involvesSequence(seq)) + if (alignCdsSequenceAsProtein(dnaSeq, protein, mappings, + dna.getGapCharacter())) { - SequenceI mapped = getAlignedTranslation(seq, gapCharacter, mapping); - if (mapped != null) - { - result.add(mapped); - } + alignedCount++; } + width = Math.max(dnaSeq.getLength(), width); } - return result; + int oldwidth; + int diff; + for (SequenceI dnaSeq : dna.getSequences()) + { + oldwidth = dnaSeq.getLength(); + diff = width - oldwidth; + if (diff > 0) + { + dnaSeq.insertCharAt(oldwidth, diff, dna.getGapCharacter()); + } + } + return alignedCount; } /** - * Returns the translation of 'seq' (as held in the mapping) with - * corresponding alignment (gaps). + * Helper method to align (if possible) the dna sequence to match the + * alignment of a mapped protein sequence. This is currently limited to + * handling coding sequence only. * - * @param seq - * @param gapCharacter - * @param mapping + * @param cdsSeq + * @param protein + * @param mappings + * @param gapChar * @return */ - protected static SequenceI getAlignedTranslation(SequenceI seq, - char gapCharacter, AlignedCodonFrame mapping) + static boolean alignCdsSequenceAsProtein(SequenceI cdsSeq, + AlignmentI protein, List mappings, + char gapChar) { - String gap = String.valueOf(gapCharacter); - boolean toDna = false; - int fromRatio = 1; - SequenceI mapTo = mapping.getDnaForAaSeq(seq); - if (mapTo != null) - { - // mapping is from protein to nucleotide - toDna = true; - // should ideally get gap count ratio from mapping - gap = String.valueOf(new char[] { gapCharacter, gapCharacter, - gapCharacter }); - } - else + SequenceI cdsDss = cdsSeq.getDatasetSequence(); + if (cdsDss == null) { - // mapping is from nucleotide to protein - mapTo = mapping.getAaForDnaSeq(seq); - fromRatio = 3; + System.err + .println("alignCdsSequenceAsProtein needs aligned sequence!"); + return false; } - StringBuilder newseq = new StringBuilder(seq.getLength() - * (toDna ? 3 : 1)); - - int residueNo = 0; // in seq, base 1 - int[] phrase = new int[fromRatio]; - int phraseOffset = 0; - int gapWidth = 0; - boolean first = true; - final Sequence alignedSeq = new Sequence("", ""); - for (char c : seq.getSequence()) + List dnaMappings = MappingUtils + .findMappingsForSequence(cdsSeq, mappings); + for (AlignedCodonFrame mapping : dnaMappings) { - if (c == gapCharacter) - { - gapWidth++; - if (gapWidth >= fromRatio) - { - newseq.append(gap); - gapWidth = 0; - } - } - else + SequenceI peptide = mapping.findAlignedSequence(cdsSeq, protein); + if (peptide != null) { - phrase[phraseOffset++] = residueNo + 1; - if (phraseOffset == fromRatio) + final int peptideLength = peptide.getLength(); + Mapping map = mapping.getMappingBetween(cdsSeq, peptide); + if (map != null) { + MapList mapList = map.getMap(); + if (map.getTo() == peptide.getDatasetSequence()) + { + mapList = mapList.getInverse(); + } + final int cdsLength = cdsDss.getLength(); + int mappedFromLength = MappingUtils.getLength(mapList + .getFromRanges()); + int mappedToLength = MappingUtils + .getLength(mapList.getToRanges()); + boolean addStopCodon = (cdsLength == mappedFromLength + * CODON_LENGTH + CODON_LENGTH) + || (peptide.getDatasetSequence() + .getLength() == mappedFromLength - 1); + if (cdsLength != mappedToLength && !addStopCodon) + { + System.err.println(String.format( + "Can't align cds as protein (length mismatch %d/%d): %s", + cdsLength, mappedToLength, cdsSeq.getName())); + } + + /* + * pre-fill the aligned cds sequence with gaps + */ + char[] alignedCds = new char[peptideLength * CODON_LENGTH + + (addStopCodon ? CODON_LENGTH : 0)]; + Arrays.fill(alignedCds, gapChar); + /* - * Have read a whole codon (or protein residue), now translate: map - * source phrase to positions in target sequence add characters at - * these positions to newseq Note mapping positions are base 1, our - * sequence positions base 0. + * walk over the aligned peptide sequence and insert mapped + * codons for residues in the aligned cds sequence */ - SearchResults sr = new SearchResults(); - for (int pos : phrase) + int copiedBases = 0; + int cdsStart = cdsDss.getStart(); + int proteinPos = peptide.getStart() - 1; + int cdsCol = 0; + + for (int col = 0; col < peptideLength; col++) { - mapping.markMappedRegion(seq, pos, sr); + char residue = peptide.getCharAt(col); + + if (Comparison.isGap(residue)) + { + cdsCol += CODON_LENGTH; + } + else + { + proteinPos++; + int[] codon = mapList.locateInTo(proteinPos, proteinPos); + if (codon == null) + { + // e.g. incomplete start codon, X in peptide + cdsCol += CODON_LENGTH; + } + else + { + for (int j = codon[0]; j <= codon[1]; j++) + { + char mappedBase = cdsDss.getCharAt(j - cdsStart); + alignedCds[cdsCol++] = mappedBase; + copiedBases++; + } + } + } } - newseq.append(sr.getCharacters()); - if (first) + + /* + * append stop codon if not mapped from protein, + * closing it up to the end of the mapped sequence + */ + if (copiedBases == cdsLength - CODON_LENGTH) { - first = false; - // Hack: Copy sequence dataset, name and description from - // SearchResults.match[0].sequence - // TODO? carry over sequence names from original 'complement' - // alignment - SequenceI mappedTo = sr.getResultSequence(0); - alignedSeq.setName(mappedTo.getName()); - alignedSeq.setDescription(mappedTo.getDescription()); - alignedSeq.setDatasetSequence(mappedTo); + for (int i = alignedCds.length - 1; i >= 0; i--) + { + if (!Comparison.isGap(alignedCds[i])) + { + cdsCol = i + 1; // gap just after end of sequence + break; + } + } + for (int i = cdsLength - CODON_LENGTH; i < cdsLength; i++) + { + alignedCds[cdsCol++] = cdsDss.getCharAt(i); + } } - phraseOffset = 0; + cdsSeq.setSequence(new String(alignedCds)); + return true; } - residueNo++; } } - alignedSeq.setSequence(newseq.toString()); - return alignedSeq; - } - - /** - * Realigns the given protein to match the alignment of the dna, using codon - * mappings to translate aligned codon positions to protein residues. - * - * @param protein - * the alignment whose sequences are realigned by this method - * @param dna - * the dna alignment whose alignment we are 'copying' - * @return the number of sequences that were realigned - */ - public static int alignProteinAsDna(AlignmentI protein, AlignmentI dna) - { - List unmappedProtein = new ArrayList(); - Map> alignedCodons = buildCodonColumnsMap( - protein, dna, unmappedProtein); - return alignProteinAs(protein, alignedCodons, unmappedProtein); + return false; } /** @@ -968,20 +1098,19 @@ public class AlignmentUtils * {dnaSequence, {proteinSequence, codonProduct}} at that position. The * comparator keeps the codon positions ordered. */ - Map> alignedCodons = new TreeMap>( + Map> alignedCodons = new TreeMap<>( new CodonComparator()); for (SequenceI dnaSeq : dna.getSequences()) { for (AlignedCodonFrame mapping : mappings) { - SequenceI prot = mapping.findAlignedSequence( - dnaSeq.getDatasetSequence(), protein); + SequenceI prot = mapping.findAlignedSequence(dnaSeq, protein); if (prot != null) { Mapping seqMap = mapping.getMappingForSequence(dnaSeq); - addCodonPositions(dnaSeq, prot, protein.getGapCharacter(), - seqMap, alignedCodons); + addCodonPositions(dnaSeq, prot, protein.getGapCharacter(), seqMap, + alignedCodons); unmappedProtein.remove(prot); } } @@ -991,9 +1120,10 @@ public class AlignmentUtils * Finally add any unmapped peptide start residues (e.g. for incomplete * codons) as if at the codon position before the second residue */ + // TODO resolve JAL-2022 so this fudge can be removed int mappedSequenceCount = protein.getHeight() - unmappedProtein.size(); addUnmappedPeptideStarts(alignedCodons, mappedSequenceCount); - + return alignedCodons; } @@ -1011,11 +1141,12 @@ public class AlignmentUtils Map> alignedCodons, int mappedSequenceCount) { - // TODO there must be an easier way! root problem is that our mapping data - // model does not include phase so can't map part of a codon to a peptide - List sequencesChecked = new ArrayList(); + // TODO delete this ugly hack once JAL-2022 is resolved + // i.e. we can model startPhase > 0 (incomplete start codon) + + List sequencesChecked = new ArrayList<>(); AlignedCodon lastCodon = null; - Map toAdd = new HashMap(); + Map toAdd = new HashMap<>(); for (Entry> entry : alignedCodons .entrySet()) @@ -1032,8 +1163,8 @@ public class AlignmentUtils AlignedCodon codon = sequenceCodon.getValue(); if (codon.peptideCol > 1) { - System.err - .println("Problem mapping protein with >1 unmapped start positions: " + System.err.println( + "Problem mapping protein with >1 unmapped start positions: " + seq.getName()); } else if (codon.peptideCol == 1) @@ -1044,8 +1175,8 @@ public class AlignmentUtils if (lastCodon != null) { AlignedCodon firstPeptide = new AlignedCodon(lastCodon.pos1, - lastCodon.pos2, lastCodon.pos3, String.valueOf(seq - .getCharAt(0)), 0); + lastCodon.pos2, lastCodon.pos3, + String.valueOf(seq.getCharAt(0)), 0); toAdd.put(seq, firstPeptide); } else @@ -1094,21 +1225,26 @@ public class AlignmentUtils List unmappedProtein) { /* - * Prefill aligned sequences with gaps before inserting aligned protein - * residues. + * prefill peptide sequences with gaps */ int alignedWidth = alignedCodons.size(); char[] gaps = new char[alignedWidth]; Arrays.fill(gaps, protein.getGapCharacter()); - String allGaps = String.valueOf(gaps); + Map peptides = new HashMap<>(); for (SequenceI seq : protein.getSequences()) { if (!unmappedProtein.contains(seq)) { - seq.setSequence(allGaps); + peptides.put(seq, Arrays.copyOf(gaps, gaps.length)); } } + /* + * Traverse the codons left to right (as defined by CodonComparator) + * and insert peptides in each column where the sequence is mapped. + * This gives a peptide 'alignment' where residues are aligned if their + * corresponding codons occupy the same columns in the cdna alignment. + */ int column = 0; for (AlignedCodon codon : alignedCodons.keySet()) { @@ -1116,12 +1252,20 @@ public class AlignmentUtils .get(codon); for (Entry entry : columnResidues.entrySet()) { - // place translated codon at its column position in sequence - entry.getKey().getSequence()[column] = entry.getValue().product - .charAt(0); + char residue = entry.getValue().product.charAt(0); + peptides.get(entry.getKey())[column] = residue; } column++; } + + /* + * and finally set the constructed sequences + */ + for (Entry entry : peptides.entrySet()) + { + entry.getKey().setSequence(new String(entry.getValue())); + } + return 0; } @@ -1181,7 +1325,7 @@ public class AlignmentUtils Map seqProduct = alignedCodons.get(codon); if (seqProduct == null) { - seqProduct = new HashMap(); + seqProduct = new HashMap<>(); alignedCodons.put(codon, seqProduct); } seqProduct.put(protein, codon); @@ -1194,7 +1338,8 @@ public class AlignmentUtils *
    *
  • One alignment must be nucleotide, and the other protein
    • *
  • At least one pair of sequences must be already mapped, or mappable
    • - *
  • Mappable means the nucleotide translation matches the protein sequence
    • + *
  • Mappable means the nucleotide translation matches the protein + * sequence
    • *
  • The translation may ignore start and stop codons if present in the * nucleotide
    • *
@@ -1250,9 +1395,10 @@ public class AlignmentUtils return false; } - SequenceI dnaDs = dnaSeq.getDatasetSequence() == null ? dnaSeq : dnaSeq - .getDatasetSequence(); - SequenceI proteinDs = proteinSeq.getDatasetSequence() == null ? proteinSeq + SequenceI dnaDs = dnaSeq.getDatasetSequence() == null ? dnaSeq + : dnaSeq.getDatasetSequence(); + SequenceI proteinDs = proteinSeq.getDatasetSequence() == null + ? proteinSeq : proteinSeq.getDatasetSequence(); for (AlignedCodonFrame mapping : mappings) @@ -1270,7 +1416,7 @@ public class AlignmentUtils * Just try to make a mapping (it is not yet stored), test whether * successful. */ - return mapProteinSequenceToCdna(proteinDs, dnaDs) != null; + return mapCdnaToProtein(proteinDs, dnaDs) != null; } /** @@ -1289,8 +1435,7 @@ public class AlignmentUtils * the alignment to check for presence of annotations */ public static void findAddableReferenceAnnotations( - List sequenceScope, - Map labelForCalcId, + List sequenceScope, Map labelForCalcId, final Map> candidates, AlignmentI al) { @@ -1317,7 +1462,7 @@ public class AlignmentUtils { continue; } - final List result = new ArrayList(); + final List result = new ArrayList<>(); for (AlignmentAnnotation dsann : datasetAnnotations) { /* @@ -1394,8 +1539,8 @@ public class AlignmentUtils /** * Set visibility of alignment annotations of specified types (labels), for - * specified sequences. This supports controls like - * "Show all secondary structure", "Hide all Temp factor", etc. + * specified sequences. This supports controls like "Show all secondary + * structure", "Hide all Temp factor", etc. * * @al the alignment to scan for annotations * @param types @@ -1412,15 +1557,18 @@ public class AlignmentUtils Collection types, List forSequences, boolean anyType, boolean doShow) { - for (AlignmentAnnotation aa : al.getAlignmentAnnotation()) + AlignmentAnnotation[] anns = al.getAlignmentAnnotation(); + if (anns != null) { - if (anyType || types.contains(aa.label)) + for (AlignmentAnnotation aa : anns) { - if ((aa.sequenceRef != null) - && (forSequences == null || forSequences - .contains(aa.sequenceRef))) + if (anyType || types.contains(aa.label)) { - aa.visible = doShow; + if ((aa.sequenceRef != null) && (forSequences == null + || forSequences.contains(aa.sequenceRef))) + { + aa.visible = doShow; + } } } } @@ -1473,242 +1621,545 @@ public class AlignmentUtils /** * Constructs an alignment consisting of the mapped (CDS) regions in the given - * nucleotide sequences, and updates mappings to match. The new sequences are - * aligned as per the original sequences (with gapped columns omitted). + * nucleotide sequences, and updates mappings to match. The CDS sequences are + * added to the original alignment's dataset, which is shared by the new + * alignment. Mappings from nucleotide to CDS, and from CDS to protein, are + * added to the alignment dataset. * * @param dna - * aligned dna sequences - * @param mappings - * from dna to protein; these are replaced with new mappings - * @param al + * aligned nucleotide (dna or cds) sequences + * @param dataset + * the alignment dataset the sequences belong to + * @param products + * (optional) to restrict results to CDS that map to specified + * protein products * @return an alignment whose sequences are the cds-only parts of the dna * sequences (or null if no mappings are found) */ public static AlignmentI makeCdsAlignment(SequenceI[] dna, - List mappings, AlignmentI al) + AlignmentI dataset, SequenceI[] products) { - List cdsColumns = findCdsColumns(dna); - - /* - * create CDS sequences and new mappings - * (from cdna to cds, and cds to peptide) - */ - List newMappings = new ArrayList(); - List cdsSequences = new ArrayList(); - char gap = al.getGapCharacter(); - - for (SequenceI dnaSeq : dna) + if (dataset == null || dataset.getDataset() != null) { - final SequenceI ds = dnaSeq.getDatasetSequence(); - List seqMappings = MappingUtils - .findMappingsForSequence(ds, mappings); - for (AlignedCodonFrame acf : seqMappings) + throw new IllegalArgumentException( + "IMPLEMENTATION ERROR: dataset.getDataset() must be null!"); + } + List foundSeqs = new ArrayList<>(); + List cdsSeqs = new ArrayList<>(); + List mappings = dataset.getCodonFrames(); + HashSet productSeqs = null; + if (products != null) + { + productSeqs = new HashSet<>(); + for (SequenceI seq : products) { - AlignedCodonFrame newMapping = new AlignedCodonFrame(); - final List mappedCds = makeCdsSequences(dnaSeq, acf, - cdsColumns, newMapping, gap); - if (!mappedCds.isEmpty()) - { - cdsSequences.addAll(mappedCds); - newMappings.add(newMapping); - } + productSeqs.add(seq.getDatasetSequence() == null ? seq : seq + .getDatasetSequence()); } } - AlignmentI newAl = new Alignment( - cdsSequences.toArray(new SequenceI[cdsSequences.size()])); /* - * add new sequences to the shared dataset, set it on the new alignment + * Construct CDS sequences from mappings on the alignment dataset. + * The logic is: + * - find the protein product(s) mapped to from each dna sequence + * - if the mapping covers the whole dna sequence (give or take start/stop + * codon), take the dna as the CDS sequence + * - else search dataset mappings for a suitable dna sequence, i.e. one + * whose whole sequence is mapped to the protein + * - if no sequence found, construct one from the dna sequence and mapping + * (and add it to dataset so it is found if this is repeated) */ - List dsseqs = al.getDataset().getSequences(); - for (SequenceI seq : newAl.getSequences()) + for (SequenceI dnaSeq : dna) { - if (!dsseqs.contains(seq.getDatasetSequence())) + SequenceI dnaDss = dnaSeq.getDatasetSequence() == null ? dnaSeq + : dnaSeq.getDatasetSequence(); + + List seqMappings = MappingUtils + .findMappingsForSequence(dnaSeq, mappings); + for (AlignedCodonFrame mapping : seqMappings) { - dsseqs.add(seq.getDatasetSequence()); + List mappingsFromSequence = mapping + .getMappingsFromSequence(dnaSeq); + + for (Mapping aMapping : mappingsFromSequence) + { + MapList mapList = aMapping.getMap(); + if (mapList.getFromRatio() == 1) + { + /* + * not a dna-to-protein mapping (likely dna-to-cds) + */ + continue; + } + + /* + * skip if mapping is not to one of the target set of proteins + */ + SequenceI proteinProduct = aMapping.getTo(); + if (productSeqs != null && !productSeqs.contains(proteinProduct)) + { + continue; + } + + /* + * try to locate the CDS from the dataset mappings; + * guard against duplicate results (for the case that protein has + * dbrefs to both dna and cds sequences) + */ + SequenceI cdsSeq = findCdsForProtein(mappings, dnaSeq, + seqMappings, aMapping); + if (cdsSeq != null) + { + if (!foundSeqs.contains(cdsSeq)) + { + foundSeqs.add(cdsSeq); + SequenceI derivedSequence = cdsSeq.deriveSequence(); + cdsSeqs.add(derivedSequence); + if (!dataset.getSequences().contains(cdsSeq)) + { + dataset.addSequence(cdsSeq); + } + } + continue; + } + + /* + * didn't find mapped CDS sequence - construct it and add + * its dataset sequence to the dataset + */ + cdsSeq = makeCdsSequence(dnaSeq.getDatasetSequence(), aMapping, + dataset).deriveSequence(); + // cdsSeq has a name constructed as CDS| + // will be either the accession for the coding sequence, + // marked in the /via/ dbref to the protein product accession + // or it will be the original nucleotide accession. + SequenceI cdsSeqDss = cdsSeq.getDatasetSequence(); + + cdsSeqs.add(cdsSeq); + + if (!dataset.getSequences().contains(cdsSeqDss)) + { + // check if this sequence is a newly created one + // so needs adding to the dataset + dataset.addSequence(cdsSeqDss); + } + + /* + * add a mapping from CDS to the (unchanged) mapped to range + */ + List cdsRange = Collections + .singletonList(new int[] + { cdsSeq.getStart(), + cdsSeq.getLength() + cdsSeq.getStart() - 1 }); + MapList cdsToProteinMap = new MapList(cdsRange, + mapList.getToRanges(), mapList.getFromRatio(), + mapList.getToRatio()); + AlignedCodonFrame cdsToProteinMapping = new AlignedCodonFrame(); + cdsToProteinMapping.addMap(cdsSeqDss, proteinProduct, + cdsToProteinMap); + + /* + * guard against duplicating the mapping if repeating this action + */ + if (!mappings.contains(cdsToProteinMapping)) + { + mappings.add(cdsToProteinMapping); + } + + propagateDBRefsToCDS(cdsSeqDss, dnaSeq.getDatasetSequence(), + proteinProduct, aMapping); + /* + * add another mapping from original 'from' range to CDS + */ + AlignedCodonFrame dnaToCdsMapping = new AlignedCodonFrame(); + final MapList dnaToCdsMap = new MapList(mapList.getFromRanges(), + cdsRange, 1, 1); + dnaToCdsMapping.addMap(dnaSeq.getDatasetSequence(), cdsSeqDss, + dnaToCdsMap); + if (!mappings.contains(dnaToCdsMapping)) + { + mappings.add(dnaToCdsMapping); + } + + /* + * transfer dna chromosomal loci (if known) to the CDS + * sequence (via the mapping) + */ + final MapList cdsToDnaMap = dnaToCdsMap.getInverse(); + transferGeneLoci(dnaSeq, cdsToDnaMap, cdsSeq); + + /* + * add DBRef with mapping from protein to CDS + * (this enables Get Cross-References from protein alignment) + * This is tricky because we can't have two DBRefs with the + * same source and accession, so need a different accession for + * the CDS from the dna sequence + */ + + // specific use case: + // Genomic contig ENSCHR:1, contains coding regions for ENSG01, + // ENSG02, ENSG03, with transcripts and products similarly named. + // cannot add distinct dbrefs mapping location on ENSCHR:1 to ENSG01 + + // JBPNote: ?? can't actually create an example that demonstrates we + // need to + // synthesize an xref. + + for (DBRefEntry primRef : dnaDss.getPrimaryDBRefs()) + { + /* + * create a cross-reference from CDS to the source sequence's + * primary reference and vice versa + */ + String source = primRef.getSource(); + String version = primRef.getVersion(); + DBRefEntry cdsCrossRef = new DBRefEntry(source, source + ":" + + version, primRef.getAccessionId()); + cdsCrossRef.setMap(new Mapping(dnaDss, new MapList(cdsToDnaMap))); + cdsSeqDss.addDBRef(cdsCrossRef); + + dnaSeq.addDBRef(new DBRefEntry(source, version, cdsSeq + .getName(), new Mapping(cdsSeqDss, dnaToCdsMap))); + + // problem here is that the cross-reference is synthesized - + // cdsSeq.getName() may be like 'CDS|dnaaccession' or + // 'CDS|emblcdsacc' + // assuming cds version same as dna ?!? + + DBRefEntry proteinToCdsRef = new DBRefEntry(source, version, + cdsSeq.getName()); + // + proteinToCdsRef.setMap(new Mapping(cdsSeqDss, cdsToProteinMap + .getInverse())); + proteinProduct.addDBRef(proteinToCdsRef); + } + + /* + * transfer any features on dna that overlap the CDS + */ + transferFeatures(dnaSeq, cdsSeq, dnaToCdsMap, null, + SequenceOntologyI.CDS); + } } } - newAl.setDataset(al.getDataset()); - /* - * Replace the old mappings with the new ones - */ - mappings.clear(); - mappings.addAll(newMappings); + AlignmentI cds = new Alignment(cdsSeqs.toArray(new SequenceI[cdsSeqs + .size()])); + cds.setDataset(dataset); - return newAl; + return cds; } /** - * Returns a consolidated list of column ranges where at least one sequence - * has a CDS feature. This assumes CDS features are on genomic sequence i.e. - * are for contiguous CDS ranges (no gaps). + * Tries to transfer gene loci (dbref to chromosome positions) from fromSeq to + * toSeq, mediated by the given mapping between the sequences * - * @param seqs - * @return + * @param fromSeq + * @param targetToFrom + * Map + * @param targetSeq */ - public static List findCdsColumns(SequenceI[] seqs) + protected static void transferGeneLoci(SequenceI fromSeq, + MapList targetToFrom, SequenceI targetSeq) { - // TODO use refactored code from AlignViewController - // markColumnsContainingFeatures, not reinvent the wheel! - - List result = new ArrayList(); - for (SequenceI seq : seqs) + if (targetSeq.getGeneLoci() != null) { - result.addAll(findCdsColumns(seq)); + // already have - don't override + return; } - - /* - * sort and compact the list into ascending, non-overlapping ranges - */ - Collections.sort(result, new Comparator() + GeneLociI fromLoci = fromSeq.getGeneLoci(); + if (fromLoci == null) { - @Override - public int compare(int[] o1, int[] o2) - { - return Integer.compare(o1[0], o2[0]); - } - }); - result = MapList.coalesceRanges(result); + return; + } - return result; - } + MapList newMap = targetToFrom.traverse(fromLoci.getMapping()); - public static List findCdsColumns(SequenceI seq) - { - List result = new ArrayList(); - SequenceOntologyI so = SequenceOntologyFactory.getInstance(); - SequenceFeature[] sfs = seq.getSequenceFeatures(); - if (sfs != null) + if (newMap != null) { - for (SequenceFeature sf : sfs) - { - if (so.isA(sf.getType(), SequenceOntologyI.CDS)) - { - int colStart = seq.findIndex(sf.getBegin()); - int colEnd = seq.findIndex(sf.getEnd()); - result.add(new int[] { colStart, colEnd }); - } - } + targetSeq.setGeneLoci(fromLoci.getSpeciesId(), + fromLoci.getAssemblyId(), fromLoci.getChromosomeId(), newMap); } - return result; } /** - * Answers true if all sequences have a gap at (or do not extend to) the - * specified column position (base 1) + * A helper method that finds a CDS sequence in the alignment dataset that is + * mapped to the given protein sequence, and either is, or has a mapping from, + * the given dna sequence. * - * @param seqs - * @param col + * @param mappings + * set of all mappings on the dataset + * @param dnaSeq + * a dna (or cds) sequence we are searching from + * @param seqMappings + * the set of mappings involving dnaSeq + * @param aMapping + * a transcript-to-peptide mapping * @return */ - public static boolean isGappedColumn(List seqs, int col) + static SequenceI findCdsForProtein(List mappings, + SequenceI dnaSeq, List seqMappings, + Mapping aMapping) { - if (seqs != null) + /* + * TODO a better dna-cds-protein mapping data representation to allow easy + * navigation; until then this clunky looping around lists of mappings + */ + SequenceI seqDss = dnaSeq.getDatasetSequence() == null ? dnaSeq + : dnaSeq.getDatasetSequence(); + SequenceI proteinProduct = aMapping.getTo(); + + /* + * is this mapping from the whole dna sequence (i.e. CDS)? + * allowing for possible stop codon on dna but not peptide + */ + int mappedFromLength = MappingUtils + .getLength(aMapping.getMap().getFromRanges()); + int dnaLength = seqDss.getLength(); + if (mappedFromLength == dnaLength + || mappedFromLength == dnaLength - CODON_LENGTH) + { + /* + * if sequence has CDS features, this is a transcript with no UTR + * - do not take this as the CDS sequence! (JAL-2789) + */ + if (seqDss.getFeatures().getFeaturesByOntology(SequenceOntologyI.CDS) + .isEmpty()) + { + return seqDss; + } + } + + /* + * looks like we found the dna-to-protein mapping; search for the + * corresponding cds-to-protein mapping + */ + List mappingsToPeptide = MappingUtils + .findMappingsForSequence(proteinProduct, mappings); + for (AlignedCodonFrame acf : mappingsToPeptide) { - for (SequenceI seq : seqs) + for (SequenceToSequenceMapping map : acf.getMappings()) { - if (!Comparison.isGap(seq.getCharAt(col - 1))) + Mapping mapping = map.getMapping(); + if (mapping != aMapping + && mapping.getMap().getFromRatio() == CODON_LENGTH + && proteinProduct == mapping.getTo() + && seqDss != map.getFromSeq()) { - return false; + mappedFromLength = MappingUtils + .getLength(mapping.getMap().getFromRanges()); + if (mappedFromLength == map.getFromSeq().getLength()) + { + /* + * found a 3:1 mapping to the protein product which covers + * the whole dna sequence i.e. is from CDS; finally check the CDS + * is mapped from the given dna start sequence + */ + SequenceI cdsSeq = map.getFromSeq(); + // todo this test is weak if seqMappings contains multiple mappings; + // we get away with it if transcript:cds relationship is 1:1 + List dnaToCdsMaps = MappingUtils + .findMappingsForSequence(cdsSeq, seqMappings); + if (!dnaToCdsMaps.isEmpty()) + { + return cdsSeq; + } + } } } } - return true; + return null; } /** - * Returns the column ranges (base 1) of each aligned sequence that are - * involved in any mapping. This is a helper method for aligning protein - * products of aligned transcripts. + * Helper method that makes a CDS sequence as defined by the mappings from the + * given sequence i.e. extracts the 'mapped from' ranges (which may be on + * forward or reverse strand). * - * @param mappedSequences - * (possibly gapped) dna sequences - * @param mappings - * @return + * @param seq + * @param mapping + * @param dataset + * - existing dataset. We check for sequences that look like the CDS + * we are about to construct, if one exists already, then we will + * just return that one. + * @return CDS sequence (as a dataset sequence) */ - protected static List> getMappedColumns( - List mappedSequences, List mappings) + static SequenceI makeCdsSequence(SequenceI seq, Mapping mapping, + AlignmentI dataset) { - List> result = new ArrayList>(); - for (SequenceI seq : mappedSequences) + /* + * construct CDS sequence name as "CDS|" with 'from id' held in the mapping + * if set (e.g. EMBL protein_id), else sequence name appended + */ + String mapFromId = mapping.getMappedFromId(); + final String seqId = "CDS|" + + (mapFromId != null ? mapFromId : seq.getName()); + + SequenceI newSeq = null; + + final MapList maplist = mapping.getMap(); + if (maplist.isContiguous() && maplist.isFromForwardStrand()) { - List columns = new ArrayList(); - List seqMappings = MappingUtils - .findMappingsForSequence(seq, mappings); - for (AlignedCodonFrame mapping : seqMappings) + /* + * just a subsequence, keep same dataset sequence + */ + int start = maplist.getFromLowest(); + int end = maplist.getFromHighest(); + newSeq = seq.getSubSequence(start - 1, end); + newSeq.setName(seqId); + } + else + { + /* + * construct by splicing mapped from ranges + */ + char[] seqChars = seq.getSequence(); + List fromRanges = maplist.getFromRanges(); + int cdsWidth = MappingUtils.getLength(fromRanges); + char[] newSeqChars = new char[cdsWidth]; + + int newPos = 0; + for (int[] range : fromRanges) { - List maps = mapping.getMappingsForSequence(seq); - for (Mapping map : maps) + if (range[0] <= range[1]) { - /* - * Get the codon regions as { [2, 5], [7, 12], [14, 14] etc } - * Find and add the overall aligned column range for each - */ - for (int[] cdsRange : map.getMap().getFromRanges()) + // forward strand mapping - just copy the range + int length = range[1] - range[0] + 1; + System.arraycopy(seqChars, range[0] - 1, newSeqChars, newPos, + length); + newPos += length; + } + else + { + // reverse strand mapping - copy and complement one by one + for (int i = range[0]; i >= range[1]; i--) { - int startPos = cdsRange[0]; - int endPos = cdsRange[1]; - int startCol = seq.findIndex(startPos); - int endCol = seq.findIndex(endPos); - columns.add(new int[] { startCol, endCol }); + newSeqChars[newPos++] = Dna.getComplement(seqChars[i - 1]); } } } - result.add(columns); + + newSeq = new Sequence(seqId, newSeqChars, 1, newPos); } - return result; + + if (dataset != null) + { + SequenceI[] matches = dataset.findSequenceMatch(newSeq.getName()); + if (matches != null) + { + boolean matched = false; + for (SequenceI mtch : matches) + { + if (mtch.getStart() != newSeq.getStart()) + { + continue; + } + if (mtch.getEnd() != newSeq.getEnd()) + { + continue; + } + if (!Arrays.equals(mtch.getSequence(), newSeq.getSequence())) + { + continue; + } + if (!matched) + { + matched = true; + newSeq = mtch; + } + else + { + System.err.println( + "JAL-2154 regression: warning - found (and ignnored a duplicate CDS sequence):" + + mtch.toString()); + } + } + } + } + // newSeq.setDescription(mapFromId); + + return newSeq; } /** - * Helper method to make cds-only sequences and populate their mappings to - * protein products - *

- * For example, if ggCCaTTcGAg has mappings [3, 4, 6, 7, 9, 10] to protein - * then generate a sequence CCTTGA with mapping [1, 6] to the same protein - * residues - *

- * Typically eukaryotic dna will include cds encoding for a single peptide - * sequence i.e. return a single result. Bacterial dna may have overlapping - * cds mappings coding for multiple peptides so return multiple results - * (example EMBL KF591215). + * Adds any DBRefEntrys to cdsSeq from contig that have a Mapping congruent to + * the given mapping. * - * @param dnaSeq - * a dna aligned sequence + * @param cdsSeq + * @param contig + * @param proteinProduct * @param mapping - * containing one or more mappings of the sequence to protein - * @param ungappedCdsColumns - * @param newMappings - * the new mapping to populate, from the cds-only sequences to their - * mapped protein sequences - * @return + * @return list of DBRefEntrys added */ - protected static List makeCdsSequences(SequenceI dnaSeq, - AlignedCodonFrame mapping, List ungappedCdsColumns, - AlignedCodonFrame newMappings, char gapChar) + protected static List propagateDBRefsToCDS(SequenceI cdsSeq, + SequenceI contig, SequenceI proteinProduct, Mapping mapping) { - List cdsSequences = new ArrayList(); - List seqMappings = mapping.getMappingsForSequence(dnaSeq); - for (Mapping seqMapping : seqMappings) - { - SequenceI cds = makeCdsSequence(dnaSeq, seqMapping, - ungappedCdsColumns, gapChar); - cds.createDatasetSequence(); - cdsSequences.add(cds); + // gather direct refs from contig congruent with mapping + List direct = new ArrayList<>(); + HashSet directSources = new HashSet<>(); - /* - * add new mappings, from dna to cds, and from cds to peptide - */ - MapList dnaToCds = addCdsMappings(dnaSeq.getDatasetSequence(), cds, - seqMapping, newMappings); + if (contig.getDBRefs() != null) + { + for (DBRefEntry dbr : contig.getDBRefs()) + { + if (dbr.hasMap() && dbr.getMap().getMap().isTripletMap()) + { + MapList map = dbr.getMap().getMap(); + // check if map is the CDS mapping + if (mapping.getMap().equals(map)) + { + direct.add(dbr); + directSources.add(dbr.getSource()); + } + } + } + } + DBRefEntry[] onSource = DBRefUtils.selectRefs( + proteinProduct.getDBRefs(), + directSources.toArray(new String[0])); + List propagated = new ArrayList<>(); - /* - * transfer any features on dna that overlap the CDS - */ - transferFeatures(dnaSeq, cds, dnaToCds, null, SequenceOntologyI.CDS); + // and generate appropriate mappings + for (DBRefEntry cdsref : direct) + { + // clone maplist and mapping + MapList cdsposmap = new MapList( + Arrays.asList(new int[][] + { new int[] { cdsSeq.getStart(), cdsSeq.getEnd() } }), + cdsref.getMap().getMap().getToRanges(), 3, 1); + Mapping cdsmap = new Mapping(cdsref.getMap().getTo(), + cdsref.getMap().getMap()); + + // create dbref + DBRefEntry newref = new DBRefEntry(cdsref.getSource(), + cdsref.getVersion(), cdsref.getAccessionId(), + new Mapping(cdsmap.getTo(), cdsposmap)); + + // and see if we can map to the protein product for this mapping. + // onSource is the filtered set of accessions on protein that we are + // tranferring, so we assume accession is the same. + if (cdsmap.getTo() == null && onSource != null) + { + List sourceRefs = DBRefUtils.searchRefs(onSource, + cdsref.getAccessionId()); + if (sourceRefs != null) + { + for (DBRefEntry srcref : sourceRefs) + { + if (srcref.getSource().equalsIgnoreCase(cdsref.getSource())) + { + // we have found a complementary dbref on the protein product, so + // update mapping's getTo + newref.getMap().setTo(proteinProduct); + } + } + } + } + cdsSeq.addDBRef(newref); + propagated.add(newref); } - return cdsSequences; + return propagated; } /** @@ -1718,14 +2169,14 @@ public class AlignmentUtils * * @param fromSeq * @param toSeq + * @param mapping + * the mapping from 'fromSeq' to 'toSeq' * @param select * if not null, only features of this type are copied (including * subtypes in the Sequence Ontology) - * @param mapping - * the mapping from 'fromSeq' to 'toSeq' * @param omitting */ - public static int transferFeatures(SequenceI fromSeq, SequenceI toSeq, + protected static int transferFeatures(SequenceI fromSeq, SequenceI toSeq, MapList mapping, String select, String... omitting) { SequenceI copyTo = toSeq; @@ -1733,199 +2184,667 @@ public class AlignmentUtils { copyTo = copyTo.getDatasetSequence(); } + if (fromSeq == copyTo || fromSeq.getDatasetSequence() == copyTo) + { + return 0; // shared dataset sequence + } + + /* + * get features, optionally restricted by an ontology term + */ + List sfs = select == null ? fromSeq.getFeatures() + .getPositionalFeatures() : fromSeq.getFeatures() + .getFeaturesByOntology(select); - SequenceOntologyI so = SequenceOntologyFactory.getInstance(); int count = 0; - SequenceFeature[] sfs = fromSeq.getSequenceFeatures(); - if (sfs != null) + for (SequenceFeature sf : sfs) { - for (SequenceFeature sf : sfs) + String type = sf.getType(); + boolean omit = false; + for (String toOmit : omitting) { - String type = sf.getType(); - if (select != null && !so.isA(type, select)) + if (type.equals(toOmit)) { - continue; + omit = true; } - boolean omit = false; - for (String toOmit : omitting) + } + if (omit) + { + continue; + } + + /* + * locate the mapped range - null if either start or end is + * not mapped (no partial overlaps are calculated) + */ + int start = sf.getBegin(); + int end = sf.getEnd(); + int[] mappedTo = mapping.locateInTo(start, end); + /* + * if whole exon range doesn't map, try interpreting it + * as 5' or 3' exon overlapping the CDS range + */ + if (mappedTo == null) + { + mappedTo = mapping.locateInTo(end, end); + if (mappedTo != null) { - if (type.equals(toOmit)) - { - omit = true; - } + /* + * end of exon is in CDS range - 5' overlap + * to a range from the start of the peptide + */ + mappedTo[0] = 1; } - if (omit) + } + if (mappedTo == null) + { + mappedTo = mapping.locateInTo(start, start); + if (mappedTo != null) { - continue; + /* + * start of exon is in CDS range - 3' overlap + * to a range up to the end of the peptide + */ + mappedTo[1] = toSeq.getLength(); } + } + if (mappedTo != null) + { + int newBegin = Math.min(mappedTo[0], mappedTo[1]); + int newEnd = Math.max(mappedTo[0], mappedTo[1]); + SequenceFeature copy = new SequenceFeature(sf, newBegin, newEnd, + sf.getFeatureGroup(), sf.getScore()); + copyTo.addSequenceFeature(copy); + count++; + } + } + return count; + } - /* - * locate the mapped range - null if either start or end is - * not mapped (no partial overlaps are calculated) - */ - int start = sf.getBegin(); - int end = sf.getEnd(); - int[] mappedTo = mapping.locateInTo(start, end); - /* - * if whole exon range doesn't map, try interpreting it - * as 5' or 3' exon overlapping the CDS range - */ - if (mappedTo == null) + /** + * Returns a mapping from dna to protein by inspecting sequence features of + * type "CDS" on the dna. A mapping is constructed if the total CDS feature + * length is 3 times the peptide length (optionally after dropping a trailing + * stop codon). This method does not check whether the CDS nucleotide sequence + * translates to the peptide sequence. + * + * @param dnaSeq + * @param proteinSeq + * @return + */ + public static MapList mapCdsToProtein(SequenceI dnaSeq, + SequenceI proteinSeq) + { + List ranges = findCdsPositions(dnaSeq); + int mappedDnaLength = MappingUtils.getLength(ranges); + + /* + * if not a whole number of codons, truncate mapping + */ + int codonRemainder = mappedDnaLength % CODON_LENGTH; + if (codonRemainder > 0) + { + mappedDnaLength -= codonRemainder; + MappingUtils.removeEndPositions(codonRemainder, ranges); + } + + int proteinLength = proteinSeq.getLength(); + int proteinStart = proteinSeq.getStart(); + int proteinEnd = proteinSeq.getEnd(); + + /* + * incomplete start codon may mean X at start of peptide + * we ignore both for mapping purposes + */ + if (proteinSeq.getCharAt(0) == 'X') + { + // todo JAL-2022 support startPhase > 0 + proteinStart++; + proteinLength--; + } + List proteinRange = new ArrayList<>(); + + /* + * dna length should map to protein (or protein plus stop codon) + */ + int codesForResidues = mappedDnaLength / CODON_LENGTH; + if (codesForResidues == (proteinLength + 1)) + { + // assuming extra codon is for STOP and not in peptide + // todo: check trailing codon is indeed a STOP codon + codesForResidues--; + mappedDnaLength -= CODON_LENGTH; + MappingUtils.removeEndPositions(CODON_LENGTH, ranges); + } + + if (codesForResidues == proteinLength) + { + proteinRange.add(new int[] { proteinStart, proteinEnd }); + return new MapList(ranges, proteinRange, CODON_LENGTH, 1); + } + return null; + } + + /** + * Returns a list of CDS ranges found (as sequence positions base 1), i.e. of + * [start, end] positions of sequence features of type "CDS" (or a sub-type of + * CDS in the Sequence Ontology). The ranges are sorted into ascending start + * position order, so this method is only valid for linear CDS in the same + * sense as the protein product. + * + * @param dnaSeq + * @return + */ + protected static List findCdsPositions(SequenceI dnaSeq) + { + List result = new ArrayList<>(); + + List sfs = dnaSeq.getFeatures().getFeaturesByOntology( + SequenceOntologyI.CDS); + if (sfs.isEmpty()) + { + return result; + } + SequenceFeatures.sortFeatures(sfs, true); + + for (SequenceFeature sf : sfs) + { + int phase = 0; + try + { + phase = Integer.parseInt(sf.getPhase()); + } catch (NumberFormatException e) + { + // ignore + } + /* + * phase > 0 on first codon means 5' incomplete - skip to the start + * of the next codon; example ENST00000496384 + */ + int begin = sf.getBegin(); + int end = sf.getEnd(); + if (result.isEmpty() && phase > 0) + { + begin += phase; + if (begin > end) + { + // shouldn't happen! + System.err + .println("Error: start phase extends beyond start CDS in " + + dnaSeq.getName()); + } + } + result.add(new int[] { begin, end }); + } + + /* + * Finally sort ranges by start position. This avoids a dependency on + * keeping features in order on the sequence (if they are in order anyway, + * the sort will have almost no work to do). The implicit assumption is CDS + * ranges are assembled in order. Other cases should not use this method, + * but instead construct an explicit mapping for CDS (e.g. EMBL parsing). + */ + Collections.sort(result, IntRangeComparator.ASCENDING); + return result; + } + + /** + * Helper method that adds a peptide variant feature. ID and + * clinical_significance attributes of the dna variant (if present) are copied + * to the new feature. + * + * @param peptide + * @param peptidePos + * @param residue + * @param var + * @param codon + * the variant codon e.g. aCg + * @param canonical + * the 'normal' codon e.g. aTg + * @return true if a feature was added, else false + */ + static boolean addPeptideVariant(SequenceI peptide, int peptidePos, + String residue, DnaVariant var, String codon, String canonical) + { + /* + * get peptide translation of codon e.g. GAT -> D + * note that variants which are not single alleles, + * e.g. multibase variants or HGMD_MUTATION etc + * are currently ignored here + */ + String trans = codon.contains("-") ? null + : (codon.length() > CODON_LENGTH ? null + : ResidueProperties.codonTranslate(codon)); + if (trans == null) + { + return false; + } + String desc = canonical + "/" + codon; + String featureType = ""; + if (trans.equals(residue)) + { + featureType = SequenceOntologyI.SYNONYMOUS_VARIANT; + } + else if (ResidueProperties.STOP.equals(trans)) + { + featureType = SequenceOntologyI.STOP_GAINED; + } + else + { + String residue3Char = StringUtils + .toSentenceCase(ResidueProperties.aa2Triplet.get(residue)); + String trans3Char = StringUtils + .toSentenceCase(ResidueProperties.aa2Triplet.get(trans)); + desc = "p." + residue3Char + peptidePos + trans3Char; + featureType = SequenceOntologyI.NONSYNONYMOUS_VARIANT; + } + SequenceFeature sf = new SequenceFeature(featureType, desc, peptidePos, + peptidePos, var.getSource()); + + StringBuilder attributes = new StringBuilder(32); + String id = (String) var.variant.getValue(VARIANT_ID); + if (id != null) + { + if (id.startsWith(SEQUENCE_VARIANT)) + { + id = id.substring(SEQUENCE_VARIANT.length()); + } + sf.setValue(VARIANT_ID, id); + attributes.append(VARIANT_ID).append("=").append(id); + // TODO handle other species variants JAL-2064 + StringBuilder link = new StringBuilder(32); + try + { + link.append(desc).append(" ").append(id).append( + "|http://www.ensembl.org/Homo_sapiens/Variation/Summary?v=") + .append(URLEncoder.encode(id, "UTF-8")); + sf.addLink(link.toString()); + } catch (UnsupportedEncodingException e) + { + // as if + } + } + String clinSig = (String) var.variant.getValue(CLINICAL_SIGNIFICANCE); + if (clinSig != null) + { + sf.setValue(CLINICAL_SIGNIFICANCE, clinSig); + attributes.append(";").append(CLINICAL_SIGNIFICANCE).append("=") + .append(clinSig); + } + peptide.addSequenceFeature(sf); + if (attributes.length() > 0) + { + sf.setAttributes(attributes.toString()); + } + return true; + } + + /** + * Makes an alignment with a copy of the given sequences, adding in any + * non-redundant sequences which are mapped to by the cross-referenced + * sequences. + * + * @param seqs + * @param xrefs + * @param dataset + * the alignment dataset shared by the new copy + * @return + */ + public static AlignmentI makeCopyAlignment(SequenceI[] seqs, + SequenceI[] xrefs, AlignmentI dataset) + { + AlignmentI copy = new Alignment(new Alignment(seqs)); + copy.setDataset(dataset); + boolean isProtein = !copy.isNucleotide(); + SequenceIdMatcher matcher = new SequenceIdMatcher(seqs); + if (xrefs != null) + { + for (SequenceI xref : xrefs) + { + DBRefEntry[] dbrefs = xref.getDBRefs(); + if (dbrefs != null) { - mappedTo = mapping.locateInTo(end, end); - if (mappedTo != null) + for (DBRefEntry dbref : dbrefs) { - /* - * end of exon is in CDS range - 5' overlap - * to a range from the start of the peptide - */ - mappedTo[0] = 1; + if (dbref.getMap() == null || dbref.getMap().getTo() == null + || dbref.getMap().getTo().isProtein() != isProtein) + { + continue; + } + SequenceI mappedTo = dbref.getMap().getTo(); + SequenceI match = matcher.findIdMatch(mappedTo); + if (match == null) + { + matcher.add(mappedTo); + copy.addSequence(mappedTo); + } } } - if (mappedTo == null) + } + } + return copy; + } + + /** + * Try to align sequences in 'unaligned' to match the alignment of their + * mapped regions in 'aligned'. For example, could use this to align CDS + * sequences which are mapped to their parent cDNA sequences. + * + * This method handles 1:1 mappings (dna-to-dna or protein-to-protein). For + * dna-to-protein or protein-to-dna use alternative methods. + * + * @param unaligned + * sequences to be aligned + * @param aligned + * holds aligned sequences and their mappings + * @return + */ + public static int alignAs(AlignmentI unaligned, AlignmentI aligned) + { + /* + * easy case - aligning a copy of aligned sequences + */ + if (alignAsSameSequences(unaligned, aligned)) + { + return unaligned.getHeight(); + } + + /* + * fancy case - aligning via mappings between sequences + */ + List unmapped = new ArrayList<>(); + Map> columnMap = buildMappedColumnsMap( + unaligned, aligned, unmapped); + int width = columnMap.size(); + char gap = unaligned.getGapCharacter(); + int realignedCount = 0; + // TODO: verify this loop scales sensibly for very wide/high alignments + + for (SequenceI seq : unaligned.getSequences()) + { + if (!unmapped.contains(seq)) + { + char[] newSeq = new char[width]; + Arrays.fill(newSeq, gap); // JBPComment - doubt this is faster than the + // Integer iteration below + int newCol = 0; + int lastCol = 0; + + /* + * traverse the map to find columns populated + * by our sequence + */ + for (Integer column : columnMap.keySet()) { - mappedTo = mapping.locateInTo(start, start); - if (mappedTo != null) + Character c = columnMap.get(column).get(seq); + if (c != null) { /* - * start of exon is in CDS range - 3' overlap - * to a range up to the end of the peptide + * sequence has a character at this position + * */ - mappedTo[1] = toSeq.getLength(); + newSeq[newCol] = c; + lastCol = newCol; } + newCol++; } - if (mappedTo != null) + + /* + * trim trailing gaps + */ + if (lastCol < width) { - SequenceFeature copy = new SequenceFeature(sf); - copy.setBegin(Math.min(mappedTo[0], mappedTo[1])); - copy.setEnd(Math.max(mappedTo[0], mappedTo[1])); - copyTo.addSequenceFeature(copy); - count++; + char[] tmp = new char[lastCol + 1]; + System.arraycopy(newSeq, 0, tmp, 0, lastCol + 1); + newSeq = tmp; } + // TODO: optimise SequenceI to avoid char[]->String->char[] + seq.setSequence(String.valueOf(newSeq)); + realignedCount++; } } - return count; + return realignedCount; } /** - * Creates and adds mappings - *

    - *
  • from cds to peptide
    • - *
  • from dna to cds
    • - *
- * and returns the dna-to-cds mapping + * If unaligned and aligned sequences share the same dataset sequences, then + * simply copies the aligned sequences to the unaligned sequences and returns + * true; else returns false * - * @param dnaSeq - * @param cdsSeq - * @param dnaMapping - * @param newMappings + * @param unaligned + * - sequences to be aligned based on aligned + * @param aligned + * - 'guide' alignment containing sequences derived from same + * dataset as unaligned * @return */ - protected static MapList addCdsMappings(SequenceI dnaSeq, - SequenceI cdsSeq, Mapping dnaMapping, - AlignedCodonFrame newMappings) + static boolean alignAsSameSequences(AlignmentI unaligned, + AlignmentI aligned) { - cdsSeq.createDatasetSequence(); + if (aligned.getDataset() == null || unaligned.getDataset() == null) + { + return false; // should only pass alignments with datasets here + } + + // map from dataset sequence to alignment sequence(s) + Map> alignedDatasets = new HashMap<>(); + for (SequenceI seq : aligned.getSequences()) + { + SequenceI ds = seq.getDatasetSequence(); + if (alignedDatasets.get(ds) == null) + { + alignedDatasets.put(ds, new ArrayList()); + } + alignedDatasets.get(ds).add(seq); + } /* - * CDS to peptide is just a contiguous 3:1 mapping, with - * the peptide ranges taken unchanged from the dna mapping + * first pass - check whether all sequences to be aligned share a + * dataset sequence with an aligned sequence; also note the leftmost + * ungapped column from which to copy */ - List cdsRanges = new ArrayList(); - SequenceI cdsDataset = cdsSeq.getDatasetSequence(); - cdsRanges.add(new int[] { 1, cdsDataset.getLength() }); - MapList cdsToPeptide = new MapList(cdsRanges, dnaMapping.getMap() - .getToRanges(), 3, 1); - newMappings.addMap(cdsDataset, dnaMapping.getTo(), cdsToPeptide); + int leftmost = Integer.MAX_VALUE; + for (SequenceI seq : unaligned.getSequences()) + { + final SequenceI ds = seq.getDatasetSequence(); + if (!alignedDatasets.containsKey(ds)) + { + return false; + } + SequenceI alignedSeq = alignedDatasets.get(ds) + .get(0); + int startCol = alignedSeq.findIndex(seq.getStart()); // 1.. + leftmost = Math.min(leftmost, startCol); + } + + /* + * second pass - copy aligned sequences; + * heuristic rule: pair off sequences in order for the case where + * more than one shares the same dataset sequence + */ + final char gapCharacter = aligned.getGapCharacter(); + for (SequenceI seq : unaligned.getSequences()) + { + List alignedSequences = alignedDatasets + .get(seq.getDatasetSequence()); + SequenceI alignedSeq = alignedSequences.get(0); + + /* + * gap fill for leading (5') UTR if any + */ + // TODO this copies intron columns - wrong! + int startCol = alignedSeq.findIndex(seq.getStart()); // 1.. + int endCol = alignedSeq.findIndex(seq.getEnd()); + char[] seqchars = new char[endCol - leftmost + 1]; + Arrays.fill(seqchars, gapCharacter); + char[] toCopy = alignedSeq.getSequence(startCol - 1, endCol); + System.arraycopy(toCopy, 0, seqchars, startCol - leftmost, + toCopy.length); + seq.setSequence(String.valueOf(seqchars)); + if (alignedSequences.size() > 0) + { + // pop off aligned sequences (except the last one) + alignedSequences.remove(0); + } + } /* - * dna 'from' ranges map 1:1 to the contiguous extracted CDS + * finally remove gapped columns (e.g. introns) */ - MapList dnaToCds = new MapList(dnaMapping.getMap().getFromRanges(), - cdsRanges, 1, 1); - newMappings.addMap(dnaSeq, cdsDataset, dnaToCds); - return dnaToCds; + new RemoveGapColCommand("", unaligned.getSequencesArray(), 0, + unaligned.getWidth() - 1, unaligned); + + return true; } /** - * Makes and returns a CDS-only sequence, where the CDS regions are identified - * as the 'from' ranges of the mapping on the dna. + * Returns a map whose key is alignment column number (base 1), and whose + * values are a map of sequence characters in that column. * - * @param dnaSeq - * nucleotide sequence - * @param seqMapping - * mappings from CDS regions of nucleotide - * @param ungappedCdsColumns + * @param unaligned + * @param aligned + * @param unmapped * @return */ - protected static SequenceI makeCdsSequence(SequenceI dnaSeq, - Mapping seqMapping, List ungappedCdsColumns, char gapChar) + static SortedMap> buildMappedColumnsMap( + AlignmentI unaligned, AlignmentI aligned, + List unmapped) { - int cdsWidth = MappingUtils.getLength(ungappedCdsColumns); + /* + * Map will hold, for each aligned column position, a map of + * {unalignedSequence, characterPerSequence} at that position. + * TreeMap keeps the entries in ascending column order. + */ + SortedMap> map = new TreeMap<>(); /* - * populate CDS columns with the aligned - * column character if that column is mapped (which may be a gap - * if an intron interrupts a codon), else with a gap + * record any sequences that have no mapping so can't be realigned */ - List fromRanges = seqMapping.getMap().getFromRanges(); - char[] cdsChars = new char[cdsWidth]; - int pos = 0; - for (int[] columns : ungappedCdsColumns) + unmapped.addAll(unaligned.getSequences()); + + List mappings = aligned.getCodonFrames(); + + for (SequenceI seq : unaligned.getSequences()) { - for (int i = columns[0]; i <= columns[1]; i++) + for (AlignedCodonFrame mapping : mappings) { - char dnaChar = dnaSeq.getCharAt(i - 1); - if (Comparison.isGap(dnaChar)) - { - cdsChars[pos] = gapChar; - } - else + SequenceI fromSeq = mapping.findAlignedSequence(seq, aligned); + if (fromSeq != null) { - int seqPos = dnaSeq.findPosition(i - 1); - if (MappingUtils.contains(fromRanges, seqPos)) + Mapping seqMap = mapping.getMappingBetween(fromSeq, seq); + if (addMappedPositions(seq, fromSeq, seqMap, map)) { - cdsChars[pos] = dnaChar; - } - else - { - cdsChars[pos] = gapChar; + unmapped.remove(seq); } } - pos++; } } - SequenceI cdsSequence = new Sequence(dnaSeq.getName(), - String.valueOf(cdsChars)); - - transferDbRefs(seqMapping.getTo(), cdsSequence); - - return cdsSequence; + return map; } /** - * Locate any xrefs to CDS databases on the protein product and attach to the - * CDS sequence. Also add as a sub-token of the sequence name. + * Helper method that adds to a map the mapped column positions of a sequence. + *
+ * For example if aaTT-Tg-gAAA is mapped to TTTAAA then the map should record + * that columns 3,4,6,10,11,12 map to characters T,T,T,A,A,A of the mapped to + * sequence. * - * @param from - * @param to + * @param seq + * the sequence whose column positions we are recording + * @param fromSeq + * a sequence that is mapped to the first sequence + * @param seqMap + * the mapping from 'fromSeq' to 'seq' + * @param map + * a map to add the column positions (in fromSeq) of the mapped + * positions of seq + * @return */ - protected static void transferDbRefs(SequenceI from, SequenceI to) + static boolean addMappedPositions(SequenceI seq, SequenceI fromSeq, + Mapping seqMap, Map> map) { - String cdsAccId = FeatureProperties.getCodingFeature(DBRefSource.EMBL); - DBRefEntry[] cdsRefs = DBRefUtils.selectRefs(from.getDBRefs(), - DBRefSource.CODINGDBS); - if (cdsRefs != null) + if (seqMap == null) + { + return false; + } + + /* + * invert mapping if it is from unaligned to aligned sequence + */ + if (seqMap.getTo() == fromSeq.getDatasetSequence()) { - for (DBRefEntry cdsRef : cdsRefs) + seqMap = new Mapping(seq.getDatasetSequence(), + seqMap.getMap().getInverse()); + } + + int toStart = seq.getStart(); + + /* + * traverse [start, end, start, end...] ranges in fromSeq + */ + for (int[] fromRange : seqMap.getMap().getFromRanges()) + { + for (int i = 0; i < fromRange.length - 1; i += 2) { - to.addDBRef(new DBRefEntry(cdsRef)); - cdsAccId = cdsRef.getAccessionId(); + boolean forward = fromRange[i + 1] >= fromRange[i]; + + /* + * find the range mapped to (sequence positions base 1) + */ + int[] range = seqMap.locateMappedRange(fromRange[i], + fromRange[i + 1]); + if (range == null) + { + System.err.println("Error in mapping " + seqMap + " from " + + fromSeq.getName()); + return false; + } + int fromCol = fromSeq.findIndex(fromRange[i]); + int mappedCharPos = range[0]; + + /* + * walk over the 'from' aligned sequence in forward or reverse + * direction; when a non-gap is found, record the column position + * of the next character of the mapped-to sequence; stop when all + * the characters of the range have been counted + */ + while (mappedCharPos <= range[1] && fromCol <= fromSeq.getLength() + && fromCol >= 0) + { + if (!Comparison.isGap(fromSeq.getCharAt(fromCol - 1))) + { + /* + * mapped from sequence has a character in this column + * record the column position for the mapped to character + */ + Map seqsMap = map.get(fromCol); + if (seqsMap == null) + { + seqsMap = new HashMap<>(); + map.put(fromCol, seqsMap); + } + seqsMap.put(seq, seq.getCharAt(mappedCharPos - toStart)); + mappedCharPos++; + } + fromCol += (forward ? 1 : -1); + } } } - if (!to.getName().contains(cdsAccId)) + return true; + } + + // strictly temporary hack until proper criteria for aligning protein to cds + // are in place; this is so Ensembl -> fetch xrefs Uniprot aligns the Uniprot + public static boolean looksLikeEnsembl(AlignmentI alignment) + { + for (SequenceI seq : alignment.getSequences()) { - to.setName(to.getName() + "|" + cdsAccId); + String name = seq.getName(); + if (!name.startsWith("ENSG") && !name.startsWith("ENST")) + { + return false; + } } + return true; } }