X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FAlignmentUtils.java;h=17aab155d78b2d468971df9f39389319b648d9d3;hb=d2b08d9048af25114cff8deabbd320471119d88d;hp=aa7cb181ee45b97937bda7c5fee15f2503783381;hpb=768a4920722ec46f7c16e35780391e39a76d02ff;p=jalview.git diff --git a/src/jalview/analysis/AlignmentUtils.java b/src/jalview/analysis/AlignmentUtils.java index aa7cb18..17aab15 100644 --- a/src/jalview/analysis/AlignmentUtils.java +++ b/src/jalview/analysis/AlignmentUtils.java @@ -22,6 +22,7 @@ package jalview.analysis; import static jalview.io.gff.GffConstants.CLINICAL_SIGNIFICANCE; +import jalview.api.DBRefEntryI; import jalview.datamodel.AlignedCodon; import jalview.datamodel.AlignedCodonFrame; import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping; @@ -39,6 +40,7 @@ import jalview.io.gff.SequenceOntologyFactory; import jalview.io.gff.SequenceOntologyI; import jalview.schemes.ResidueProperties; import jalview.util.Comparison; +import jalview.util.DBRefUtils; import jalview.util.MapList; import jalview.util.MappingUtils; import jalview.util.StringUtils; @@ -850,6 +852,11 @@ public class AlignmentUtils */ public static int alignProteinAsDna(AlignmentI protein, AlignmentI dna) { + if (protein.isNucleotide() || !dna.isNucleotide()) + { + System.err.println("Wrong alignment type in alignProteinAsDna"); + return 0; + } List unmappedProtein = new ArrayList(); Map> alignedCodons = buildCodonColumnsMap( protein, dna, unmappedProtein); @@ -857,6 +864,162 @@ public class AlignmentUtils } /** + * Realigns the given dna to match the alignment of the protein, using codon + * mappings to translate aligned peptide positions to codons. + * + * @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 + */ + public static int alignCdsAsProtein(AlignmentI dna, AlignmentI protein) + { + 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; + for (SequenceI dnaSeq : dna.getSequences()) + { + if (alignCdsSequenceAsProtein(dnaSeq, protein, mappings, + dna.getGapCharacter())) + { + alignedCount++; + } + } + return alignedCount; + } + + /** + * 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 cdsSeq + * @param protein + * @param mappings + * @param gapChar + * @return + */ + static boolean alignCdsSequenceAsProtein(SequenceI cdsSeq, + AlignmentI protein, List mappings, char gapChar) + { + SequenceI cdsDss = cdsSeq.getDatasetSequence(); + if (cdsDss == null) + { + System.err + .println("alignCdsSequenceAsProtein needs aligned sequence!"); + return false; + } + + List dnaMappings = MappingUtils + .findMappingsForSequence(cdsSeq, mappings); + for (AlignedCodonFrame mapping : dnaMappings) + { + SequenceI peptide = mapping.findAlignedSequence(cdsSeq, protein); + int peptideLength = peptide.getLength(); + if (peptide != null) + { + Mapping map = mapping.getMappingBetween(cdsSeq, peptide); + if (map != null) + { + MapList mapList = map.getMap(); + if (map.getTo() == peptide.getDatasetSequence()) + { + mapList = mapList.getInverse(); + } + int cdsLength = cdsDss.getLength(); + int mappedFromLength = MappingUtils.getLength(mapList + .getFromRanges()); + int mappedToLength = MappingUtils + .getLength(mapList.getToRanges()); + boolean addStopCodon = (cdsLength == mappedFromLength * 3 + 3) + || (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 * 3 + + (addStopCodon ? 3 : 0)]; + Arrays.fill(alignedCds, gapChar); + + /* + * walk over the aligned peptide sequence and insert mapped + * codons for residues in the aligned cds sequence + */ + char[] alignedPeptide = peptide.getSequence(); + char[] nucleotides = cdsDss.getSequence(); + int copiedBases = 0; + int cdsStart = cdsDss.getStart(); + int proteinPos = peptide.getStart() - 1; + int cdsCol = 0; + for (char residue : alignedPeptide) + { + if (Comparison.isGap(residue)) + { + cdsCol += 3; + } + else + { + proteinPos++; + int[] codon = mapList.locateInTo(proteinPos, proteinPos); + if (codon == null) + { + // e.g. incomplete start codon, X in peptide + cdsCol += 3; + } + else + { + for (int j = codon[0]; j <= codon[1]; j++) + { + char mappedBase = nucleotides[j - cdsStart]; + alignedCds[cdsCol++] = mappedBase; + copiedBases++; + } + } + } + } + + /* + * append stop codon if not mapped from protein, + * closing it up to the end of the mapped sequence + */ + if (copiedBases == nucleotides.length - 3) + { + 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 = nucleotides.length - 3; i < nucleotides.length; i++) + { + alignedCds[cdsCol++] = nucleotides[i]; + } + } + cdsSeq.setSequence(new String(alignedCds)); + return true; + } + } + } + return false; + } + + /** * Builds a map whose key is an aligned codon position (3 alignment column * numbers base 0), and whose value is a map from protein sequence to each * protein's peptide residue for that codon. The map generates an ordering of @@ -1404,9 +1567,9 @@ public class AlignmentUtils * added to the alignment dataset. * * @param dna - * aligned dna sequences + * aligned nucleotide (dna or cds) sequences * @param dataset - * - throws error if not given a dataset + * the alignment dataset the sequences belong to * @param products * (optional) to restrict results to CDS that map to specified * protein products @@ -1414,20 +1577,21 @@ public class AlignmentUtils * sequences (or null if no mappings are found) */ public static AlignmentI makeCdsAlignment(SequenceI[] dna, - AlignmentI dataset, AlignmentI products) + AlignmentI dataset, SequenceI[] products) { - if (dataset.getDataset() != null) + if (dataset == null || dataset.getDataset() != null) { - throw new Error( + 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.getSequences()) + for (SequenceI seq : products) { productSeqs.add(seq.getDatasetSequence() == null ? seq : seq .getDatasetSequence()); @@ -1435,24 +1599,32 @@ public class AlignmentUtils } /* - * construct CDS sequences from the (cds-to-protein) mappings made earlier; - * this makes it possible to model multiple products from dna (e.g. EMBL); - * however it does mean we don't have the EMBL protein_id (a property on - * the CDS features) in order to make the CDS sequence name :-( + * 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) */ - for (SequenceI seq : dna) + for (SequenceI dnaSeq : dna) { - SequenceI seqDss = seq.getDatasetSequence() == null ? seq : seq - .getDatasetSequence(); + SequenceI dnaDss = dnaSeq.getDatasetSequence() == null ? dnaSeq + : dnaSeq.getDatasetSequence(); + List seqMappings = MappingUtils - .findMappingsForSequence(seq, mappings); + .findMappingsForSequence(dnaSeq, mappings); for (AlignedCodonFrame mapping : seqMappings) { - List mappingsFromSequence = mapping.getMappingsFromSequence(seq); + List mappingsFromSequence = mapping + .getMappingsFromSequence(dnaSeq); for (Mapping aMapping : mappingsFromSequence) { - if (aMapping.getMap().getFromRatio() == 1) + MapList mapList = aMapping.getMap(); + if (mapList.getFromRatio() == 1) { /* * not a dna-to-protein mapping (likely dna-to-cds) @@ -1461,55 +1633,33 @@ public class AlignmentUtils } /* - * check for an existing CDS sequence i.e. a 3:1 mapping to - * the dna mapping's product + * skip if mapping is not to one of the target set of proteins */ - SequenceI cdsSeq = null; - - // TODO better mappings collection data model so we can do - // a direct lookup instead of double loops to find mappings - SequenceI proteinProduct = aMapping.getTo(); - - /* - * skip if not mapped to one of a specified set of proteins - */ if (productSeqs != null && !productSeqs.contains(proteinProduct)) { continue; } - for (AlignedCodonFrame acf : MappingUtils - .findMappingsForSequence(proteinProduct, mappings)) + /* + * 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) { - for (SequenceToSequenceMapping map : acf.getMappings()) + if (!foundSeqs.contains(cdsSeq)) { - if (map.getMapping().getMap().getFromRatio() == 3 - && proteinProduct == map.getMapping().getTo() - && seqDss != map.getFromSeq()) + foundSeqs.add(cdsSeq); + SequenceI derivedSequence = cdsSeq.deriveSequence(); + cdsSeqs.add(derivedSequence); + if (!dataset.getSequences().contains(cdsSeq)) { - /* - * found a 3:1 mapping to the protein product which is not - * from the dna sequence...assume it is from the CDS sequence - * TODO mappings data model that brings together related - * dna-cds-protein mappings in one object - */ - cdsSeq = map.getFromSeq(); + dataset.addSequence(cdsSeq); } } - } - if (cdsSeq != null) - { - /* - * mappings are always to dataset sequences so create an aligned - * sequence to own it; add the dataset sequence to the dataset - */ - SequenceI derivedSequence = cdsSeq.deriveSequence(); - cdsSeqs.add(derivedSequence); - if (!dataset.getSequences().contains(cdsSeq)) - { - dataset.addSequence(cdsSeq); - } continue; } @@ -1517,7 +1667,7 @@ public class AlignmentUtils * didn't find mapped CDS sequence - construct it and add * its dataset sequence to the dataset */ - cdsSeq = makeCdsSequence(seq.getDatasetSequence(), aMapping); + cdsSeq = makeCdsSequence(dnaSeq.getDatasetSequence(), aMapping); SequenceI cdsSeqDss = cdsSeq.createDatasetSequence(); cdsSeqs.add(cdsSeq); if (!dataset.getSequences().contains(cdsSeqDss)) @@ -1530,11 +1680,10 @@ public class AlignmentUtils */ List cdsRange = Collections.singletonList(new int[] { 1, cdsSeq.getLength() }); - MapList map = new MapList(cdsRange, aMapping.getMap() - .getToRanges(), aMapping.getMap().getFromRatio(), - aMapping.getMap().getToRatio()); + MapList cdsToProteinMap = new MapList(cdsRange, mapList.getToRanges(), + mapList.getFromRatio(), mapList.getToRatio()); AlignedCodonFrame cdsToProteinMapping = new AlignedCodonFrame(); - cdsToProteinMapping.addMap(cdsSeq, proteinProduct, map); + cdsToProteinMapping.addMap(cdsSeq, proteinProduct, cdsToProteinMap); /* * guard against duplicating the mapping if repeating this action @@ -1545,22 +1694,59 @@ public class AlignmentUtils } /* + * copy protein's dbrefs to CDS sequence + * this enables Get Cross-References from CDS alignment + */ + DBRefEntry[] proteinRefs = DBRefUtils.selectDbRefs(false, + proteinProduct.getDBRefs()); + if (proteinRefs != null) + { + for (DBRefEntry ref : proteinRefs) + { + DBRefEntry cdsToProteinRef = new DBRefEntry(ref); + cdsToProteinRef.setMap(new Mapping(proteinProduct, + cdsToProteinMap)); + cdsSeqDss.addDBRef(cdsToProteinRef); + } + } + + /* * add another mapping from original 'from' range to CDS */ - AlignedCodonFrame dnaToProteinMapping = new AlignedCodonFrame(); - map = new MapList(aMapping.getMap().getFromRanges(), cdsRange, 1, + AlignedCodonFrame dnaToCdsMapping = new AlignedCodonFrame(); + MapList dnaToCdsMap = new MapList(mapList.getFromRanges(), + cdsRange, 1, 1); - dnaToProteinMapping.addMap(seq.getDatasetSequence(), cdsSeq, map); - if (!mappings.contains(dnaToProteinMapping)) + dnaToCdsMapping.addMap(dnaSeq.getDatasetSequence(), cdsSeq, + dnaToCdsMap); + if (!mappings.contains(dnaToCdsMapping)) { - mappings.add(dnaToProteinMapping); + mappings.add(dnaToCdsMapping); } + /* + * 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 + */ + DBRefEntryI dnaRef = dnaDss.getSourceDBRef(); + if (dnaRef != null) + { + // assuming cds version same as dna ?!? + DBRefEntry proteinToCdsRef = new DBRefEntry(dnaRef.getSource(), + dnaRef.getVersion(), cdsSeq.getName()); + proteinToCdsRef.setMap(new Mapping(cdsSeqDss, cdsToProteinMap + .getInverse())); + proteinProduct.addDBRef(proteinToCdsRef); + } /* * transfer any features on dna that overlap the CDS */ - transferFeatures(seq, cdsSeq, map, null, SequenceOntologyI.CDS); + transferFeatures(dnaSeq, cdsSeq, cdsToProteinMap, null, + SequenceOntologyI.CDS); } } } @@ -1573,6 +1759,83 @@ public class AlignmentUtils } /** + * 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 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 + * an initial candidate from seqMappings + * @return + */ + static SequenceI findCdsForProtein(List mappings, + SequenceI dnaSeq, List seqMappings, + Mapping aMapping) + { + /* + * 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 - 3) + { + 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 (SequenceToSequenceMapping map : acf.getMappings()) + { + Mapping mapping = map.getMapping(); + if (mapping != aMapping && mapping.getMap().getFromRatio() == 3 + && proteinProduct == mapping.getTo() + && seqDss != map.getFromSeq()) + { + 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 it + * is from the dna start sequence + */ + SequenceI cdsSeq = map.getFromSeq(); + List dnaToCdsMaps = MappingUtils + .findMappingsForSequence(cdsSeq, seqMappings); + if (!dnaToCdsMaps.isEmpty()) + { + return cdsSeq; + } + } + } + } + } + return null; + } + + /** * 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). @@ -1609,8 +1872,15 @@ public class AlignmentUtils } } - SequenceI newSeq = new Sequence(seq.getName() + "|" - + mapping.getTo().getName(), newSeqChars, 1, newPos); + /* + * assign 'from id' held in the mapping if set (e.g. EMBL protein_id), + * else generate a sequence name + */ + String mapFromId = mapping.getMappedFromId(); + String seqId = "CDS|" + (mapFromId != null ? mapFromId : seq.getName()); + SequenceI newSeq = new Sequence(seqId, newSeqChars, 1, newPos); + // newSeq.setDescription(mapFromId); + return newSeq; } @@ -2265,6 +2535,17 @@ public class AlignmentUtils */ 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); @@ -2317,6 +2598,54 @@ public class AlignmentUtils } /** + * 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 unaligned + * @param aligned + * @return + */ + static boolean alignAsSameSequences(AlignmentI unaligned, + AlignmentI aligned) + { + if (aligned.getDataset() == null || unaligned.getDataset() == null) + { + return false; // should only pass alignments with datasets here + } + + Map alignedDatasets = new HashMap(); + for (SequenceI seq : aligned.getSequences()) + { + alignedDatasets.put(seq.getDatasetSequence(), seq); + } + + /* + * first pass - check whether all sequences to be aligned share a dataset + * sequence with an aligned sequence + */ + for (SequenceI seq : unaligned.getSequences()) + { + if (!alignedDatasets.containsKey(seq.getDatasetSequence())) + { + return false; + } + } + + /* + * second pass - copy aligned sequences + */ + for (SequenceI seq : unaligned.getSequences()) + { + SequenceI alignedSequence = alignedDatasets.get(seq + .getDatasetSequence()); + seq.setSequence(alignedSequence.getSequenceAsString()); + } + + return true; + } + + /** * Returns a map whose key is alignment column number (base 1), and whose * values are a map of sequence characters in that column. *