Welcome, Guest. Please Login or Register
UGENE Bulletin Board
  Welcome to our forum.
  HomeHelpSearchLoginRegister  
 
 
Pages: 1 2 3 
Улучшение плагина Repeat Finder (Read 33416 times)
Feb 25th, 2013 at 7:00pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Добрый день,

начну со знакомства. Я по профессии программист, и мое хобби биоинформатика. О вашем проекте недавно узнал на хабрахабре, после публикации одного обзора (ссылки дать не могу) . Точнее ваше ПО у меня валялось давно, но теперь я узнал, что вы русскоязычная команда, разрабатывающая открытый проект и готовы к сотрудничеству. Поэтому в принципе я готов читать исходный код и помогать в выполнении того о чем тут договоримся. Но я программирую только под Windows, и предпочитаю C#, но могу программировать и на С++ в Visual Studio. (я поговорил с Иваном Новиковым, который с вами работал, и он мне пояснил, что возможно с вами договорится о сотрудничестве)

О моих проектах по биоинформатике можете посмотреть тут - (ссылку дать запрещают) Smiley

Теперь с формальной стороной закончим и перейдем к сути дела.

У меня есть целый ряд идей, но лучше начать с чего-то простого, но более конкретного. Вот у вас есть такой плагин Repeat Finder - на мой взгляд он сделан плохо, и я его не смог бы использовать скажем для моего эксперимента, который описан тут (опять ссылка Smiley )
Хотя это как раз то самое, что нужно для этого эксперимента - найти в геноме все одинаковые строки (подпоследовательности) скажем более 50 символов.

Ровно такой же код с использование суффиксного дерева (наврал) массива я и использовал у себя. Но там есть тоже некоторые проблемки.

Поэтому я с одной стороны, хотел бы понять как работает это у вас - расскажите где исходники для этого плагина, какой класс:метод смотреть?
С другой, хотел бы понять заинтересованны ли вы в его улучшении? Так лишь к примеру - я так и не смог получить список всех повторяющихся последовательностей, хотя совершенно вторичную информацию, где находятся эти последовательности получил. (это лишь пример, если же делать по уму - я раскритикую это более сильно и с деталями. Но критика это поймите - доброжелательная, я был бы тут даже заинтересован помочь сделать/улучшить с кем то в паре к примеру).
« Last Edit: Feb 27th, 2013 at 6:27am by SergeyJ »  
IP Logged
 
Reply #1 - Feb 26th, 2013 at 5:38pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
Сергей,

ваша заинтересованность в UGENE - хорошая новость для нас!

Хотелось бы все таки посмотреть на ваши проекты и описания экспериментов. Пожалуйста, вышлите ссылки к нам на почту (ugene [at] unipro [dot] ru). Мы сможем ознакомиться с этим и понять, где у нас общие интересы.

UGENE реализован на C++, с использованием фреймворка Qt 4. Я не знаю, рассказал ли вам Иван Новиков, как это собирать. Инструкции есть в ugene/build.txt или мы можем написать вам подробно.

Конечно мы заинтересованы в улучшении UGENE! Наверняка у вас есть свои идеи по поводу реализации алгоритма поиска повторов и, возможно, вам известны каки-нибудь подводные камни, которые мы могли упустить. Код лежит вот тут (ugene\src\plugins\repeat_finder\src\ ). Реализацию алгоритма поиска повторов с использованием суффиксного массива(не дерева) можно найти в этих файлах: RFSArray. Также обратите внимание на файлы RF_SuffixArray, RFBase, RFDiagonal

Причина, по которой мы используем регионы может быть следующей. Из позиций повторяющихся последовательностей мы легко можем получить сами последовательности. Наоборот уже сложнее. Таких специфичных задач очень много, поэтому мы стараемся предоставлять более общие решения и прибегать к C++ как можно реже. В UGENE есть такой инструмент - Workflow Designer. Где можно создавать многостадийные схемы обработки данных. Можно создать и схему, которая решает вашу задачу (я вложил ее). Вам нужно установить входные и выходные файлы, поменять параметры, если нужно и запустить схему. На выходе она выдаст повторяющиеся последовательности, но только когда мы поправим один небольшой баг (https://ugene.unipro.ru/tracker/browse/UGENE-1466)...

Да, действительно, команда у нас русская, а базируемся мы в Новосибирске Smiley
 
IP Logged
 
Reply #2 - Feb 26th, 2013 at 6:56pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Попробую добавить ссылку с описанием некоторых моих проектов

biogenom.eu (вроде получилось Wink )

"Причина, по которой мы используем регионы может быть следующей. Из позиций повторяющихся последовательностей мы легко можем получить сами последовательности. Наоборот уже сложнее."

Это то понятно. И одно другому не мешает. Но на сколько я понял - поправьте если я не прав - списка повторяющих последовательностей я не могу получить так?

Вы достаточно много потратили на визуализацию того, где эти повторы есть, а результата то и нет Smiley Поясню. Рассматривать где эти повторы есть для генома - вряд ли кто-то будет. Часто (за исключением вырожденных, скорее даже тренировочных задач) геном большой, даже для бактерии это 1-6 миллионов символов, и множество повторов. Для чего их ищут (ответьте вы, наверное есть подзадачи которые вы имели введу, когда это реализовывали, а я пока сужу со своей точки зрения) ? Мне же они нужны сразу целиком. И думаю для многих тоже нужно также, а по одной-две никто не будет рассматривать. Поэтому самое простое, что нужно - это записать все найденные повторные последовательности - ну например просто в формате .fasta, и конечно вторичной информацией могут быть то где эти последовательности найдены (скажем как комментарий к найденной последовательности в фасте).

Отсюда вопрос:
1. Возможно ли вообще мне получить этот список на данный момент (т.е. может я просто не понимаю как? тогда расскажите последовательность действий)
2. Для дружественного интерфейса - это не должно выглядеть как многостадийная обработка - это самое элементарное - ищу повторяющиеся последовательности - задаю параметры - получаю собственно то что ищу.

Теперь о подводных камнях. По сути визуально вы рисуете сам тот суффиксный массив. Но если там только суффиксный массив - то этого мало. Я могу ошибаться, но я опишу одну тонкость - и вы скажите решена ли она у вас и как.
Часто нужны непересекающиеся повторы. Т.е. если есть последовательность banana, и скажем интересует длина 2 и более, то что вы дадите:
ana будет считаться повтором?
какую последовательность вы выберите na или an ?


Да, Иван Новиков рассказал как это собирать и далее отправил к вам Smiley Пошел посмотрю ваш код, позже отпишусь.

« Last Edit: Feb 27th, 2013 at 9:19am by SergeyJ »  
IP Logged
 
Reply #3 - Feb 27th, 2013 at 7:42am

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Я не добрался посмотреть под дебагером, смотрел просто код. Но скажу, что понять его сложновато. Конечно, это первое впечатление, и понятно, что я не знаю видимо базовых классов, что сообразить.

Но пару вопросов: правильно я понимаю, что когда уже нажимается кнопка искать (для суффиксного массива) - срабатывает метод RFSArrayWAlgorithm::calculate(RFSArrayWSubtask* t) ?

Что собой представляют класс RFSArrayWSubtask ? И далее по коду есть класс CheckEdge ? Еще вы бы мне помогли, если подсказали бы в какой структуре хранится ДНК последовательность (т.е. где исходные данные, и как они попадают в метод (т.к. не через параметры - что несколько не хорошо на мой взгляд)) ?

И более общие вопросы: код вы сами пишите с нуля, или заимствуете частично из открытого кода других проектов? В частности как на счет именного этого плагина и что меня будет интересовать потом - 3D визуализатора .pdb файлов (третичных структур)? И как вы в принципе относитеть к такому заимствованию?

Просто в коде есть комментарий "Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA." - какое к этому вы имеете отношение (или это какая то стандартная отсылка по вопросам лицензирования?).

И пару вопросов по стилю:
1. Как вы относитесь к комментированию кода вообще, и к русским комментариям в частности (они у вас запрещены?)
2. На сколько для вас принципиально важен стиль расстановки скобок:

мой метод {
тра-тата
}

и допустим ли такой:

мой метод
{
тра-тата
}
 
IP Logged
 
Reply #4 - Feb 28th, 2013 at 3:44pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
Сергей,

я не без интереса посмотрел ваш сайт. Мне очень понравилось насколько полно там описаны ваши работы. В стиле "Сейчас мы вам кратко объясним что такое филогинетические деревья. А теперь перейдем к нашим разработкам". Я еще не все прочитал, но я уже успел посочувствовать РНК в ее мучительном фолдинге Smiley

По поводу наших алгоритмов.
Из аннотаций можно получить последовательности повторов. Нужно выбрать нужные аннотации или сразу всю группу в редакторе аннотаций под Sequence View и через контекстное меню экспортировать последовательности под аннотациями в файл.

В последовательности banan (или GATATA) мы найдем только непересекающиеся повторы и все повторы. То есть результатом будет и an и na, а пользователь уже пусть сам решит, какой его больше инетресует.


По поводу кода.
Да, в коде UGENE есть сложные моменты, но поиск повторов далеко не самый сложный участок, он просто требует какого-то времени для понимания.

1. Все равно алгоритмические участки выделены в отдельные модули и там работа идет с обычными типами дпнных в основном. И да, запускается  RFSArrayWAlgorithm::calculate(RFSArrayWSubtask* t).

2. RFSArrayWSubtask. У нас каждая задача запускается в отдельном потоке и RFSArrayWSubtask это подкласс-задача, которая запускает алгоритм поиска.

3.  CheckEdge. Мы создали эти классы, потому что последовательность бьется на подпоследовательности при поиске для параллельного запуска, а на стыках возникали проблемы.

4. ДНК последовательность хранится в базе (U2Sequence). Но ее можно достать впамять (DNASequence). Потом получить последовательность, как массив символов, которые так и передаются алгоритму через параметры.

5. Код поиска повторов и код визуализиации 3D структур - наши разработки. Мы заимствуем код некоторых других алгоритмов, но оставляем ссылку на автора. Потому что лицензия позволяет

6. Все, что видно извне (документации, код, баг-трекер, форум) должно быть на английском. К скобкам не придираемся. Лично мне нравится Java-style.

 
IP Logged
 
Reply #5 - Feb 28th, 2013 at 5:41pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Вот пример не самого удачного поиска. Тут (code.google.com/p/vlabdownload/downloads/detail?name=NC_000117.fna.txt&can=2&q=
#makechanges) геном одной бактерии. Ищем повторы более 50 символов.

UGENE
среди прочего находит

repeat_unit join(531463..531612,531613..531762)
/repeat_len=150
/repeat_dist=0
/repeat_homology(%)=100
repeat_unit join(531467..531616,531617..531766)
/repeat_len=150
/repeat_dist=0
/repeat_homology(%)=100

хотя на самом деле тут повторяется последовательность на 154 символа:
AGTGGTGGTGCAGCAGCAGCACTCAATTCTCTAAGAGGCTCCTCCTACAGCAATTATGACGATGCTGCTGCTGATTACGA
GCCGATAAGAACTACTGAAAATATTTATGAGAGTATTGGTGGCTCTAGAACAAGTGGCCCAGAAAATACGAGTG

И проблема тут как следствие banana. Вы показываете два варианта: 1. они почему то сокращаются до 150 символов 2. Конечно на любителя - но эти два вариант идут не как альтернативы - а как равноправные вместе с другими. На мой взгляд альтернативы нужно исключать (как минимум помечать) - возможно по тому или иному принципу, который выберет пользователь. А так это просто недоисключенные внутренние повторы.

И еще вопрос - вы исключаете вложенные повторы отдельно от алгоритма поиска повторов (у вас есть в доп. настройках галочка - "не исключать вложенные повторы" для этого )? Это разные методы? Где можно найти код именно исключения вложенных повторов, и как вы его делаете вкратце можете рассказать? (просто именно тут, кажется может крыться некоторые нюансы).


Еще вот какое дело, попробовал я создать т.н. "вычислительную схему", т.е. поискать повторы в двух геномах, и записать аннотации. В итоге нашел в одном геноме 2, а во втором 0. Что явно не соответствует тому, что он ищет в ручном режиме.

Это какой то баг? Или я что-то не так сделал (даже не знаю что, если займетесь отошлю исходные данные, чтобы вы могли воспроизвести)
 
IP Logged
 
Reply #6 - Feb 28th, 2013 at 6:23pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
Сергей,

код исключения вложенных повторов лежит тут ugene\src\plugins\repeat_finder\src\FindRepeatsTask::filterNestedRepeats. Посмотрите, пожалуйста.

Повтор, который вы скопировали пересекается на AGTG. Вообще это корректно -  считать пересекающиеся повторы повторами?

А то, что схема не работает - это плохо... Проверьте, пожалуйста, параметры элемента Find Repeats. Если они совпадают с теми, что вы выставляете, когда используете диалог, но результаты разные, то это баг. Тогда вышлите исходные данные?

 
IP Logged
 
Reply #7 - Feb 28th, 2013 at 6:54pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Действительно со схемой устойчивый результат, я даже упростил. Попробуйте создать схему для указанного выше генома NC_000117.fna.txt, ищем более 50 символов, остальное все по умолчанию. Находит только 2 последовательности. Если у вас другой результат получится - будем думать почему у меня не так Undecided

Что касается пересекающихся повторов - то думаю это зависит от задачи экспериментатора (скажем для альтернативной трансляции, сплайсинга - важно изучить такого рода частичные пересечения). Этим как и дублирующими в примере banana - an, na, надо уметь управлять.

Скажем, у меня исключение повторов ориентировалось на максимальную длину. У вас видимо на жесткость не пересечения последовательностей. Я допускаю что нужно и то и другое.
 
IP Logged
 
Reply #8 - Feb 28th, 2013 at 7:27pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
В любом случае, если у вас будет время/желание улучшить наш алгоритм  поиска повторов или какую-нибудь другую часть UGENE - пожалуйста. Мы включим ваш патч в ближайший релиз, а они у нас выходят часто. Даже если у вас появятся какие-нибудь идеи по улучшению - смело нам пишите!

А вы запускаете схему, которую я вложил в пост выше? Или вы просто собрали схему (Прочить последовательность)->(Найти повторы)->(Записать последовательность).

Я только что собрал второй вариант и проверил (вложено). Нашлось столько же повторов, сколько и в Sequence View - 6 пар. Проверьте, может у вас формат выходного файла стоит fasta. А нужно поставить тот, который поддерживает аннотации (genbank). Я добавлю issue, чтобы выводился warning, если пользователь пытается записать аннотации в формет, который их не поддерживает.
 
IP Logged
 
Reply #9 - Feb 28th, 2013 at 10:47pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
попробуйте приложенную схему. Ваша у меня ТОЖЕ не работает. И у меня в ручном режиме находит 8 пар. Кстати, версия UGENE 1.11.4

repeat_unit join(51645..51712,51753..51820)
                  /repeat_len=68
                  /repeat_dist=40
                  /repeat_homology(%)=50
repeat_unit join(51734..51799,51842..51907)
                  /repeat_len=66
                  /repeat_dist=42
                  /repeat_homology(%)=50
repeat_unit join(531361..531461,531661..531761)
                  /repeat_len=101
                  /repeat_dist=199
                  /repeat_homology(%)=50
repeat_unit join(531361..531461,531511..531611)
                  /repeat_len=101
                  /repeat_dist=49
                  /repeat_homology(%)=50
repeat_unit join(531463..531612,531613..531762)
                  /repeat_len=150
                  /repeat_dist=0
                  /repeat_homology(%)=100
repeat_unit join(531467..531616,531617..531766)
                  /repeat_len=150
                  /repeat_dist=0
                  /repeat_homology(%)=100
repeat_unit join(853782..858690,875828..880736)
                  /repeat_len=4909
                  /repeat_dist=17137
                  /repeat_homology(%)=50
repeat_unit join(858699..859256,880744..881301)
                  /repeat_len=558
                  /repeat_dist=21487
                  /repeat_homology(%)=100


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

Еще не понятно что значит repeat_homology = 50% ?
« Last Edit: Mar 1st, 2013 at 8:18am by SergeyJ »  

test.uwl (5 KB | )
IP Logged
 
Reply #10 - Mar 1st, 2013 at 1:01pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
Я запустил вложенную схему. Сначала думал, что русские трансляции с ума сходят, но оказалось нет. Я запустил ее и у меня получился файл с аннотациями. Там 6 повторов, последние два из тех 8ми, что у вас находит не нашлись, потому что максимальное расстояние у них больше, чем в схеме указано. Последовательности там нету, потому что для этого нужно выбрать элемент Write Sequence. А у вас вобще никакого резлультат эта схема не выдает? Даже файл не создается?

Я убрал фильтр по максимальному расстояние в ручном режиме и у меня такой же результат как у вас получился.

50% homology это баг(https://ugene.unipro.ru/tracker/browse/UGENE-1474). Это процент гомологии между повторами. Мы допускаем какой-то процент замен, но в этом случае он неправильно показывается.

Я правильно понимаю, что вы хотите сделать фильтр, который в последовательности banana оставит только na или an? Или вы хотите модифицировать так, чтобы ana считалось повтором?
 
IP Logged
 
Reply #11 - Mar 1st, 2013 at 1:28pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Нет файл создается и находит две последовательности.

Я кажется понял в чем дело - там по умолчанию выставляется минимальная дистанция = 0, и поэтому он находит только такие. Еще повезло, что в примере как раз есть такое.

И там в схеме нельзя выставить "не ограничивать" (и по хорошему это и должно быть по умолчанию). В то время как для максимальной дистанции можно.
 
IP Logged
 
Reply #12 - Mar 1st, 2013 at 1:52pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Что касается фильтра. Там я предполагаю сделать следующие

http://biogenom.eu/?p=383

Т.е. исключить такие повторы, которые содержатся внутри других найденных повторов. Т.е. получим список уникальных повторов без частичного вхождения одной в другую.

Т.е. в примере banana, будет найдена только ana, а na и an будет отфильтровано.

А в примере в геноме NC_000117 не будет последовательностей длиной 101 и 150 символов, а будет только на 154. Т.к. эти 4 последовательности на 101, 150 символов, так или иначе содержатся в последовательности 154.
 
IP Logged
 
Reply #13 - Mar 1st, 2013 at 2:32pm

Yuriy Vaskin   Offline
Global Moderator

Gender: male
Posts: 138
*****
 
Спасибо. Я тогда постараюсь что-нибудь сделать с параметрами, чтобы они были совпадающие с диалоговым окном и попробую другие значения по умолчанию.

Ок, я понял, что вы хотите сделать. Если у вас будут какие-нибудь вопросы - пишите, пожалуйста.
 
IP Logged
 
Reply #14 - Mar 1st, 2013 at 2:42pm

SergeyJ   Offline
YaBB Newbies

Posts: 29
*
 
Yuriy Vaskin wrote on Mar 1st, 2013 at 2:32pm:
Ок, я понял, что вы хотите сделать. Если у вас будут какие-нибудь вопросы - пишите, пожалуйста.


Т.е. Вы согласны встроить такой фильтр в UGENE?

Еще я не писал серьезные диалоговые окна на C++, и смотрю вы использует тут файлы .ui . Чем Вы их редактируете? Есть какой нибудь визуальный редактор под windows ?
Разобрался вопрос снят.
 
IP Logged
 
Pages: 1 2 3