Как определить конечное местоположение (x,y,z) определенной последовательности в 3D-области

Question

У меня есть протеиновый 3D Creo-EM скан, такой, что он содержит цепь, которая изгибается и крутится вокруг себя - и имеет в 3-мерном пространстве 2 окончания цепи (как непрерывная веревка). Мне нужно обнаружить (x,y,z) местоположение в данном пространстве куба двух или, возможно, множителя 2 концов. Пространство кубического сканирования представлено плотностями в каждом вокселе (в диапазоне от 0 до 1), полученными сканирующим ЭМ-микроскопом, так что "существующее вещество" дает значения ближе к 1, а "неважно" дает значения плотности ближе к 0. Мне нужно метод определения белковых "веревочных" ребер (возможное определение "веревочного окончания" - отсутствие продолжения в определенном запутанном направлении. Интуитивно я думаю, что может быть как минимум 2 метода: 1) определенный метод в теории графов (я не могу указать точно - если вы знаете один - пожалуйста, назовите или опишите его. 2) Производные от аналитической алгебры - но опять же я не могу указать конкретное отношение - поэтому, пожалуйста, назовите или объясните один. Пожалуйста, укажите сложность вычислений предлагаемого метода. Мой проект реализован на Python. Пожалуйста помоги. Заранее спасибо.

Answer 1

Один из подходов состоит в том, чтобы выбрать пороговую плотность, преобразовать все вокселы ниже этого порога в 0 и все выше него в 1, а затем искать пару 1-вокселей, у которых самый короткий путь самый длинный среди всех пар 1-вокселей. Эти два вокселя должны находиться вблизи концов самой длинной "веревки", независимо от точной формы, которую принимает веревка.

Вы можете определить график, в котором есть вершина для каждого 1-вокселя и ребро между каждым 1-вокселем и его 6 (или, возможно, 14) соседями. Затем вы можете вычислить длины кратчайших путей между некоторой заданной вершиной u и любой другой вершиной в O(|V|) времени и пространстве, используя поиск в ширину (здесь нам не нужны Dijkstra или Floyd-Warshall, так как каждое ребро имеет вес 1). Повторение этого для каждой возможной начальной вершины u дает алгоритм времени O(|V|^2). Пока вы делаете это, следите за самой дальней парой.

Если ваше пространство вокселей имеет w*h*d ячеек, в графе может быть w*h*d вершин (если каждый отдельный воксел является 1-вокселем), поэтому это может занять O(w^2*h^2*) г ^ 2) время в худшем случае, что, вероятно, довольно много. К счастью, есть много способов ускорить это, если вы можете позволить себе немного неточный ответ:

• Вычислять только кратчайшие пути из начальных вершин, которые находятся на границе, то есть тех вершин, которые имеют менее 6 (или 14) соседей. (Я считаю, что это не принесет в жертву оптимальное решение.)
• В качестве альтернативы, сначала "скелетизируйте" граф, многократно избавляясь от всех таких граничных вершин, удаление которых не будет разъединять граф.
• Хороший порядок выбора начальных вершин состоит в том, чтобы сначала выбрать любую вершину, а затем всегда выбирать вершину, которая была найдена на максимально возможном расстоянии от последней (и которая еще, конечно, еще не пробовалась). Это должно дать вам очень хорошее приближение к самому длинному кратчайшему пути после всего 3 итераций: самая дальняя вершина от начальной вершины будет около одного из двух концов веревки, а самая дальняя вершина от этой вершины будет около другого конца!

Примечание. Если между изогнутыми точками, находящимися рядом друг с другом, из-за изгиба нет промежутка между полными вокселями, то кратчайшие пути будут "закорачиваться" через эти ложные соединения и, возможно, снижать точность. Вы могли бы улучшить это, увеличив порог. OTOH, если порог слишком высок, то веревка может отсоединиться. Я ожидаю, что вы хотите выбрать самый высокий порог, который приводит только к 1 подключенному компоненту.

Answer 2

Если вы хотите перечислить каждый непрерывный путь (получая, таким образом, концы каждого пути) в своем трехмерном сканировании, вы можете для каждой позиции применить базовый поиск в глубину, например:

//applied at some voxel
dfs(...)
    for each surrounding voxel 
        dfs(...)

Или подробно:

class coordinate{
    x
    y
    z
    visited
}

initialize pathList
initialize coords

add all coordinates which contain "matter" to coords

dfs(coordinate,path)
    coordinate.visited = TRUE
    isEnd = TRUE
    FOR each coordinate
        //check each of the 26 possible locations (total 26 conditionals)
        IF coordinate.get(x-1,y-1,z+1) IN coords AND 
           NOT coordinate.get(x-1,y-1,z+1).visited THEN
            isEnd = FALSE
            path += coordinate.get(x-1,y-1,z+1)
            dfs(coordinate.get(x-1,y-1,z+1),path)
        ...
        IF coordinate.get(x+1,y+1,z-1) IN coords AND 
           NOT coordinate.get(x+1,y+1,z-1).visited THEN 
            isEnd = FALSE
            path += coordinate.get(x+1,y+1,z-1) 
            dfs(coordinate.get(x+1,y+1,z-1),path)
    IF isEnd THEN
        add path to pathList
    remove coordinate from coords

WHILE coords isn't empty
    dfs(coords.get(0),"")

Общая процедура (dfs) хорошо документирована на десятках других сайтов, но если вы хотите протестировать ее, вот несколько грубых Java (я не слишком знаком с Python), который отражает то, что выше:

public class C {

    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<String> paths = new ArrayList<>();



    static class Coordinate {
        int x, y, z;
        boolean visited;
        Coordinate(int x,int y,int z){
            this.x = x;
            this.y = y;
            this.z = z;
            visited = false;
        }

        public String toString() {
            return "("+x+","+y+","+z+")";
        }
    }



    void dfs(Coordinate c,String path) {
        c.visited=true;
        path+=c.toString();
        boolean isEnd = true;
        //apply dfs to 26 possible neighbors
        for(int x = c.x-1; x <= c.x+1; x++) {
            for (int y = c.y-1; y <= c.y+1; y++) {
                for (int z = c.z+1; z >= c.z-1; z--) {
                    Coordinate coord = getCoordinate(x,y,z);
                    //if coord exists and it's not been visited
                    if(coord!=null && !coord.visited && !coord.equals(c)) {
                        isEnd = false;
                        dfs(coord, path);
                    }
                }
            }
        }
        if(isEnd) paths.add(path);

        coords.remove(c);
    }

    Coordinate getCoordinate(int x,int y,int z){
        for(Coordinate b: coords){
            if(x==b.x && y==b.y && z==b.z) return b;
        }
        return null;
    }


    void search(){
        //while there are points in 3d space extend a path from one
        while(!coords.isEmpty()){
            dfs(coords.get(0),"");
        }
    }




    public static void main(String[] args) {

        C coord = new C();

        //for each place where there exists matter
        //create a coordinate object and add to coords
        // for example:
        coord.coords.add(new Coordinate(0,0,0));
        coord.coords.add(new Coordinate(-1,1,1));
        coord.coords.add(new Coordinate(1,1,1));
        coord.coords.add(new Coordinate(-1,2,2));
        coord.coords.add(new Coordinate(-1,0,2));
        coord.coords.add(new Coordinate(1,2,2));
        coord.coords.add(new Coordinate(1,0,2));

        coord.search();
        //print out each path on separate line, 
        //the path endings can easily be obtained from this 
        for(String s:coord.paths) System.out.println(s);

    }
}