su_block_multiple_alignment.cpp

ncbi源码

        return false;

    int requestedShift, actualShift = 0, width = 0;

    // slightly different behaviour when dragging from unaligned to aligned...
    if (!blockFrom->IsAligned()) {
        unsigned int fromSeqIndex, toSeqIndex;
        GetSequenceAndIndexAt(fromAlignmentIndex, row, justification, NULL, &fromSeqIndex, NULL);
        GetSequenceAndIndexAt(toAlignmentIndex, row, justification, NULL, &toSeqIndex, NULL);
        if (fromSeqIndex == eUndefined || toSeqIndex == eUndefined)
            return false;
        requestedShift = toSeqIndex - fromSeqIndex;
    }

    // vs. dragging from aligned
    else {
        requestedShift = toAlignmentIndex - fromAlignmentIndex;
    }

    const Block::Range *prevRange = NULL, *nextRange = NULL, *range = ABlock->GetRangeOfRow(row);
    if (prevUABlock) prevRange = prevUABlock->GetRangeOfRow(row);
    if (nextUABlock) nextRange = nextUABlock->GetRangeOfRow(row);
    if (requestedShift > 0) {
        if (prevUABlock)
            width = prevRange->to - prevRange->from + 1;
        actualShift = (width > requestedShift) ? requestedShift : width;
    } else {
        if (nextUABlock)
            width = nextRange->to - nextRange->from + 1;
        actualShift = (width > -requestedShift) ? requestedShift : -width;
    }
    if (actualShift == 0) return false;

    TRACE_MESSAGE("shifting row " << row << " by " << actualShift);

    ABlock->SetRangeOfRow(row, range->from - actualShift, range->to - actualShift);

    if (prevUABlock) {
        prevUABlock->SetRangeOfRow(row, prevRange->from, prevRange->to - actualShift);
        prevUABlock->m_width = 0;
        for (unsigned int i=0; i<NRows(); ++i) {
            prevRange = prevUABlock->GetRangeOfRow(i);
            width = prevRange->to - prevRange->from + 1;
            if (width < 0)
                ERROR_MESSAGE("BlockMultipleAlignment::ShiftRow() - negative width on left");
            if ((unsigned int) width > prevUABlock->m_width)
                prevUABlock->m_width = width;
        }
        if (prevUABlock->m_width == 0) {
            TRACE_MESSAGE("removing zero-m_width unaligned block on left");
            RemoveBlock(prevUABlock);
        }
    } else {
        TRACE_MESSAGE("creating unaligned block on left");
        prevUABlock = CreateNewUnalignedBlockBetween(GetBlockBefore(ABlock), ABlock);
        InsertBlockBefore(prevUABlock, ABlock);
    }

    if (nextUABlock) {
        nextUABlock->SetRangeOfRow(row, nextRange->from - actualShift, nextRange->to);
        nextUABlock->m_width = 0;
        for (unsigned int i=0; i<NRows(); ++i) {
            nextRange = nextUABlock->GetRangeOfRow(i);
            width = nextRange->to - nextRange->from + 1;
            if (width < 0)
                ERROR_MESSAGE("BlockMultipleAlignment::ShiftRow() - negative width on right");
            if ((unsigned int) width > nextUABlock->m_width)
                nextUABlock->m_width = width;
        }
        if (nextUABlock->m_width == 0) {
            TRACE_MESSAGE("removing zero-m_width unaligned block on right");
            RemoveBlock(nextUABlock);
        }
    } else {
        TRACE_MESSAGE("creating unaligned block on right");
        nextUABlock = CreateNewUnalignedBlockBetween(ABlock, GetBlockAfter(ABlock));
        InsertBlockAfter(ABlock, nextUABlock);
    }

    if (!CheckAlignedBlock(ABlock))
        ERROR_MESSAGE("BlockMultipleAlignment::ShiftRow() - shift failed to create valid aligned block");

    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::SplitBlock(unsigned int alignmentIndex)
{
    const BlockInfo& info = m_blockMap[alignmentIndex];
    if (!info.block->IsAligned() || info.block->m_width < 2 || info.blockColumn == 0)
        return false;

    TRACE_MESSAGE("splitting block");
    UngappedAlignedBlock *newAlignedBlock = new UngappedAlignedBlock(this);
    newAlignedBlock->m_width = info.block->m_width - info.blockColumn;
    info.block->m_width = info.blockColumn;

    const Block::Range *range;
    unsigned int oldTo;
    for (unsigned int row=0; row<NRows(); ++row) {
        range = info.block->GetRangeOfRow(row);
        oldTo = range->to;
        info.block->SetRangeOfRow(row, range->from, range->from + info.block->m_width - 1);
        newAlignedBlock->SetRangeOfRow(row, oldTo - newAlignedBlock->m_width + 1, oldTo);
    }

    InsertBlockAfter(info.block, newAlignedBlock);
    if (!CheckAlignedBlock(info.block) || !CheckAlignedBlock(newAlignedBlock))
        ERROR_MESSAGE("BlockMultipleAlignment::SplitBlock() - split failed to create valid m_blocks");

    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::MergeBlocks(unsigned int fromAlignmentIndex, unsigned int toAlignmentIndex)
{
    Block
        *expandedBlock = m_blockMap[fromAlignmentIndex].block,
        *lastBlock = m_blockMap[toAlignmentIndex].block;
    if (expandedBlock == lastBlock)
        return false;
    unsigned int i;
    for (i=fromAlignmentIndex; i<=toAlignmentIndex; ++i)
        if (!m_blockMap[i].block->IsAligned())
            return false;

    TRACE_MESSAGE("merging block(s)");
    for (i=0; i<NRows(); ++i)
        expandedBlock->SetRangeOfRow(i, expandedBlock->GetRangeOfRow(i)->from, lastBlock->GetRangeOfRow(i)->to);
    expandedBlock->m_width = lastBlock->GetRangeOfRow(0)->to - expandedBlock->GetRangeOfRow(0)->from + 1;

    Block *deletedBlock = NULL, *blockToDelete;
    for (i=fromAlignmentIndex; i<=toAlignmentIndex; ++i) {
        blockToDelete = m_blockMap[i].block;
        if (blockToDelete == expandedBlock)
            continue;
        if (blockToDelete != deletedBlock) {
            deletedBlock = blockToDelete;
            RemoveBlock(blockToDelete);
        }
    }

    if (!CheckAlignedBlock(expandedBlock))
        ERROR_MESSAGE("BlockMultipleAlignment::MergeBlocks() - merge failed to create valid block");

    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::CreateBlock(unsigned int fromAlignmentIndex, unsigned int toAlignmentIndex,
    eUnalignedJustification justification)
{
    const BlockInfo& info = m_blockMap[fromAlignmentIndex];
    UnalignedBlock *prevUABlock = dynamic_cast<UnalignedBlock*>(info.block);
    if (!prevUABlock || info.block != m_blockMap[toAlignmentIndex].block)
        return false;
    unsigned int row, seqIndexFrom, seqIndexTo,
        newBlockWidth = toAlignmentIndex - fromAlignmentIndex + 1,
        origWidth = prevUABlock->m_width;
    vector < unsigned int > seqIndexesFrom(NRows()), seqIndexesTo(NRows());
    const Sequence *seq;
	bool ignored;
    for (row=0; row<NRows(); ++row) {
        if (!GetSequenceAndIndexAt(fromAlignmentIndex, row, justification, &seq, &seqIndexFrom, &ignored) ||
                !GetSequenceAndIndexAt(toAlignmentIndex, row, justification, &seq, &seqIndexTo, &ignored) ||
                seqIndexFrom < 0 || seqIndexTo < 0 ||
                seqIndexTo - seqIndexFrom + 1 != newBlockWidth)
            return false;
        seqIndexesFrom[row] = seqIndexFrom;
        seqIndexesTo[row] = seqIndexTo;
    }

    TRACE_MESSAGE("creating new aligned and unaligned blocks");

    UnalignedBlock *nextUABlock = new UnalignedBlock(this);
    UngappedAlignedBlock *ABlock = new UngappedAlignedBlock(this);
    prevUABlock->m_width = nextUABlock->m_width = 0;

    bool deletePrevUABlock = true, deleteNextUABlock = true;
    const Block::Range *prevRange;
    int rangeWidth;
    for (row=0; row<NRows(); ++row) {
        prevRange = prevUABlock->GetRangeOfRow(row);

        nextUABlock->SetRangeOfRow(row, seqIndexesTo[row] + 1, prevRange->to);
        rangeWidth = prevRange->to - seqIndexesTo[row];
        if (rangeWidth < 0)
            ERROR_MESSAGE("BlockMultipleAlignment::CreateBlock() - negative nextRange width");
        else if (rangeWidth > 0) {
            if ((unsigned int) rangeWidth > nextUABlock->m_width)
                nextUABlock->m_width = rangeWidth;
            deleteNextUABlock = false;
        }

        prevUABlock->SetRangeOfRow(row, prevRange->from, seqIndexesFrom[row] - 1);
        rangeWidth = seqIndexesFrom[row] - prevRange->from;
        if (rangeWidth < 0)
            ERROR_MESSAGE("BlockMultipleAlignment::CreateBlock() - negative prevRange width");
        else if (rangeWidth > 0) {
            if ((unsigned int) rangeWidth > prevUABlock->m_width)
                prevUABlock->m_width = rangeWidth;
            deletePrevUABlock = false;
        }

        ABlock->SetRangeOfRow(row, seqIndexesFrom[row], seqIndexesTo[row]);
    }

    ABlock->m_width = newBlockWidth;
    if (prevUABlock->m_width + ABlock->m_width + nextUABlock->m_width != origWidth)
        ERROR_MESSAGE("BlockMultipleAlignment::CreateBlock() - bad block m_widths sum");

    InsertBlockAfter(prevUABlock, ABlock);
    InsertBlockAfter(ABlock, nextUABlock);
    if (deletePrevUABlock) {
        TRACE_MESSAGE("deleting zero-width unaligned block on left");
        RemoveBlock(prevUABlock);
    }
    if (deleteNextUABlock) {
        TRACE_MESSAGE("deleting zero-width unaligned block on right");
        RemoveBlock(nextUABlock);
    }

    if (!CheckAlignedBlock(ABlock))
        ERROR_MESSAGE("BlockMultipleAlignment::CreateBlock() - failed to create valid block");

    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::DeleteBlock(unsigned int alignmentIndex)
{
    Block *block = m_blockMap[alignmentIndex].block;
    if (!block || !block->IsAligned())
        return false;

    TRACE_MESSAGE("deleting block");
    Block
        *prevBlock = GetBlockBefore(block),
        *nextBlock = GetBlockAfter(block);

    // unaligned m_blocks on both sides - note that total alignment m_width can change!
    if (prevBlock && !prevBlock->IsAligned() && nextBlock && !nextBlock->IsAligned()) {
        const Block::Range *prevRange, *nextRange;
        unsigned int maxWidth = 0, width;
        for (unsigned int row=0; row<NRows(); ++row) {
            prevRange = prevBlock->GetRangeOfRow(row);
            nextRange = nextBlock->GetRangeOfRow(row);
            width = nextRange->to - prevRange->from + 1;
            prevBlock->SetRangeOfRow(row, prevRange->from, nextRange->to);
            if (width > maxWidth)
                maxWidth = width;
        }
        prevBlock->m_width = maxWidth;
        TRACE_MESSAGE("removing extra unaligned block");
        RemoveBlock(nextBlock);
    }

    // unaligned block on left only
    else if (prevBlock && !prevBlock->IsAligned()) {
        const Block::Range *prevRange, *range;
        for (unsigned int row=0; row<NRows(); ++row) {
            prevRange = prevBlock->GetRangeOfRow(row);
            range = block->GetRangeOfRow(row);
            prevBlock->SetRangeOfRow(row, prevRange->from, range->to);
        }
        prevBlock->m_width += block->m_width;
    }

    // unaligned block on right only
    else if (nextBlock && !nextBlock->IsAligned()) {
        const Block::Range *range, *nextRange;
        for (unsigned int row=0; row<NRows(); ++row) {
            range = block->GetRangeOfRow(row);
            nextRange = nextBlock->GetRangeOfRow(row);
            nextBlock->SetRangeOfRow(row, range->from, nextRange->to);
        }
        nextBlock->m_width += block->m_width;
    }

    // no adjacent unaligned m_blocks
    else {
        TRACE_MESSAGE("creating new unaligned block");
        Block *newBlock = CreateNewUnalignedBlockBetween(prevBlock, nextBlock);
        if (prevBlock)
            InsertBlockAfter(prevBlock, newBlock);
        else if (nextBlock)
            InsertBlockBefore(newBlock, nextBlock);
        else
            m_blocks.push_back(CRef<Block>(newBlock));
    }

    RemoveBlock(block);
    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::DeleteAllBlocks(void)
{
    if (m_blocks.size() == 0)
        return false;

    m_blocks.clear();
    InitCache();
    AddUnalignedBlocks();   // one single unaligned block for whole alignment
    UpdateBlockMap();
    return true;
}

bool BlockMultipleAlignment::DeleteRow(unsigned int row)
{
    if (row >= NRows()) {
        ERROR_MESSAGE("BlockMultipleAlignment::DeleteRow() - row out of range");
        return false;
    }

    // remove sequence from list
    SequenceList::iterator s = m_sequences.begin();
    for (unsigned int i=0; i<row; ++i)
        ++s;
    m_sequences.erase(s);

    // delete row from all m_blocks, removing any zero-m_width m_blocks
    BlockList::iterator b = m_blocks.begin(), br, be = m_blocks.end();
    while (b != be) {
        (*b)->DeleteRow(row);
        if ((*b)->m_width == 0) {
            br = b;
            ++b;
            TRACE_MESSAGE("deleting block resized to zero width");
            RemoveBlock(*br);
        } else
            ++b;
    }

    // update total alignment m_width
    UpdateBlockMap();
    InitCache();

    return true;
}

void BlockMultipleAlignment::GetUngappedAlignedBlocks(UngappedAlignedBlockList *uabs) const
{
    uabs->clear();
    uabs->reserve(m_blocks.size());
    BlockList::const_iterator b, be = m_blocks.end();
    for (b=m_blocks.begin(); b!=be; ++b) {
        const UngappedAlignedBlock *uab = dynamic_cast<const UngappedAlignedBlock*>(b->GetPointer());
        if (uab)
            uabs->push_back(uab);
    }
    uabs->resize(uabs->size());
}

void BlockMultipleAlignment::GetModifiableUngappedAlignedBlocks(ModifiableUngappedAlignedBlockList *uabs)
{
    uabs->clear();
    uabs->reserve(m_blocks.size());
    BlockList::iterator b, be = m_blocks.end();
    for (b=m_blocks.begin(); b!=be; ++b) {
        UngappedAlignedBlock *uab = dynamic_cast<UngappedAlignedBlock*>(b->GetPointer());
        if (uab)
            uabs->push_back(uab);
    }
    uabs->resize(uabs->size());
}

bool BlockMultipleAlignment::ExtractRows(
    const vector < unsigned int >& slavesToRemove, AlignmentList *pairwiseAlignments)
{
    if (slavesToRemove.size() == 0) return false;

    // make a bool list of rows to remove, also checking to make sure slave list items are in range
    unsigned int i;
    vector < bool > removeRows(NRows(), false);
    for (i=0; i<slavesToRemove.size(); ++i) {
        if (slavesToRemove[i] > 0 && slavesToRemove[i] < NRows()) {
            removeRows[slavesToRemove[i]] = true;
        } else {
            ERROR_MESSAGE("BlockMultipleAlignment::ExtractRows() - can't extract row "
                << slavesToRemove[i]);
            return false;
        }
    }

    if (pairwiseAlignments) {
        TRACE_MESSAGE("creating new pairwise alignments");
        SetDiagPostLevel(eDiag_Warning);    // otherwise, info messages take a long time if lots of rows

        UngappedAlignedBlockList uaBlocks;
        GetUngappedAlignedBlocks(&uaBlocks);
        UngappedAlignedBlockList::const_iterator u, ue = uaBlocks.end();

        for (i=0; i<slavesToRemove.size(); ++i) {

            // create new pairwise alignment from each removed row
            SequenceList newSeqs(2);
            newSeqs[0] = m_sequences[0];
            newSeqs[1] = m_sequences[slavesToRemove[i]];
            BlockMultipleAlignment *newAlignment = new BlockMultipleAlignment(newSeqs);
            for (u=uaBlocks.begin(); u!=ue; ++u) {
                UngappedAlignedBlock *newABlock = new UngappedAlignedBlock(newAlignment);
                const Block::Range *range = (*u)->GetRangeOfRow(0);
                newABlock->SetRangeOfRow(0, range->from, range->to);
                range = (*u)->GetRangeOfRow(slavesToRemove[i]);
                newABlock->SetRangeOfRow(1, range->from, range->to);
                newABlock->m_width = range->to - range->from + 1;
                newAlignment->AddAlignedBlockAtEnd(newABlock);
            }
            if (!newAlignment->AddUnalignedBlocks() ||
                !newAlignment->UpdateBlockMap()) {
                ERROR_MESSAGE("BlockMultipleAlignment::ExtractRows() - error creating new alignment");
                return false;
            }

            pairwiseAlignments->push_back(newAlignment);
        }
        SetDiagPostLevel(eDiag_Info);
    }

    // remove sequences
    TRACE_MESSAGE("deleting sequences");
    VectorRemoveElements(m_sequences, removeRows, slavesToRemove.size());